How to efficiently remove redundant linear constraints for optimization?

Question

My optimization problem involves thousands of linear constraints. I want to reduce the complexity of my problem by finding redundant constraints, e.g. 3 * x + 4 * y < 10 would be redundant if I already have a constraint that is 4 * x + 5 * y < 10 (and x and y are >= 0, which is the case for my problem).

So, I have a numpy array that holds all the coefficients, and it looks like this, for example:

[[0.1, 3.0, 4.8, 0.2],
 [1.0, 4.7, 5.3, 0.1],
 [2.2, 4.3, 5.2, 1.1]]

representing the constraints:

0.1 * w + 3.0 * x + 4.8 * y + 0.2 * z < 10
1.0 * w + 4.7 * x + 5.3 * y + 0.1 * z < 10
2.2 * w + 4.3 * x + 5.2 * y + 1.1 * z < 10

How do I efficiently find out which one are redundant?

My common sense tells me to do a loop (pseudo-codeish):

for i, row1 in enumerate(array):
    for j, row2 in enumerate(array):
        if j > i:
            if all(row1 > row2):
                delete row

But this slow for thousands of constraints. Any way to speed it up?

Answer 1

You can think of each constraint as a hyperplane, intercepting each axis at (sum constraint constant) / (coefficient for that axis); if the coefficient is 0, the hyperplane is parallel to that axis (== "intercepts at infinity").

Trivially, if the axis-intercepts for one hyperplane are all equal to or greater than the corresponding intercepts for another, that hyperplane is redundant.

In order to cull as many constraints as early as possible, you want to start by comparing against ones whose hyperplane is (a) as close to the origin as possible and (b) parallel to as few axes as possible, as it can only cull other hyperplanes also parallel to that axis. [A hyperplane not parallel to a given axis may be able to cull one parallel to that axis, but the inverse is never true.]

I suggest you sort the list by (number of axis-parallel axes) then (sum of non-infinite axis intercepts).