Algorithm for simplifying a set of linear inequalities

Question

I am looking for an algorithm that, given a set of linear inequalities in $m$ variables, returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of inequalities. If finding an optimal solution is computationally-hard, then a heuristic solution, that applies some reasonable simplification rules, would also be fine. As an example, given the inequalities:

$$ x + y \geq 1$$ $$ x + y \leq 0$$

the algorithm should return the empty set. Given the inequalities:

$$ x + y \geq 1$$ $$ 2 x + 2 y \geq 3$$

the algorithm should return e.g.

$$ 2 x + 2 y \geq 3$$

A Google search for "simplifying linear inequalities" yielded graphical solutions for two variables, e.g. here and here. I am not looking for a graphical solution but for a logical solution in the form of a small set of equivalent inequalities.

The first example shouldn't return the empty set. Maybe you meant $x + y \leq 0$ in the second equation? — ktnr, Dec 07 '20 at 20:45
Fourier-Motzkin elimination may also be relevant. See https://en.wikipedia.org/wiki/Fourier%E2%80%93Motzkin_elimination — ErlingMOSEK, Dec 08 '20 at 08:37
Are you looking for exact arithmetic algorithms or floating point will do? — Konstantin, Dec 22 '20 at 13:59
@Konstantin My main application is proving theorems, so exact solutions are required. But floating point solutions are also interesting as an approximation. — Erel Segal-Halevi, Dec 22 '20 at 15:11

score 10 · Accepted Answer · answered Dec 07 '20 at 23:34

What I'm about to suggest is less sophisticated than (and presumably less efficient than) the presolvers Mark L. Stone mentions, but would be relatively easy to implement (assuming you have an LP solver). It assumes that the variables are continuous, not discrete. For simplicity, I'll assume that all inequalities are of the form $a_i'x \ge b_i$ ($i=1,\dots,N$). For each $i$ in turn, minimize $a_i' x$ subject to the other surviving inequalities. If the minimum is greater than or equal to $b_i$, inequality $i$ is redundant and is dropped. Otherwise, it is kept.

score 6 · Answer 2 · answered Dec 07 '20 at 19:24

6

It sounds like you want something along the lines of a (partial) presolve, which most commercial solvers implement.

For example, Gurobi has a presolve accessible from the Python interface which should do what you want, and maybe more. https://support.gurobi.com/hc/en-us/articles/360024738352-How-does-presolve-work- I suppose you can provide a model just containing the desired variable declarations and inequalities.

If you provide a model having redundant ineqqalities to a solver having presolve, it should by default execute its presolve as the first step of its solution process, without first requiring a separate call by the user to the presolve.

answered Dec 07 '20 at 19:24

Mark L. Stone

13,392
1
31
67

Thanks! Do you know if there is a "presolve" function in an open-source solver? Alternatively, are there published algorithms for presolve? – Erel Segal-Halevi Dec 08 '20 at 09:42
1

Have a look into SCIP and publications from its developers. – ktnr Dec 08 '20 at 11:54
Here's an oldie but goodie on presolve, which is freely available. "Experience with a Primal Presolve Algorithm - Robert Fourer and David M. Gay, April 23, 1993 https://ampl.com/REFS/pripre.pdf – Mark L. Stone Dec 08 '20 at 21:04

Konstantin · Answer 3 · 2020-12-22T19:27:13.603

I have some experience with theoretical work around large systems of inequalities, and I found these packages very useful:

lrslib - computational geometry package, in exact arithmetics, created by David Avis from McGill University. One of its key functionalities is redund - quick and efficient removal of redundant inequalities from an H-representaion of a convex polytope. There is also an option to do this in parallel.
normaliz - another amazing project that I found very useful in working with large systems of inequalities in exact arithmetics.

The functionalities of the two packages have a partial overlap, but the implementations differ. I found that they complemented each other nicely as the shapes and sizes of the inputs varied.

score 2 · Answer 4 · answered Jan 08 '21 at 14:41

Sometimes it already helps to know the name of a problem. From a more theoretical point of view, i believe that there is a community working on your problem. I know the problem you describe under the term: constraint propagation.

For an introduction check for instance: http://www.cs.unibo.it/~gabbri/MaterialeCorsi/CP@CS.pdf

Algorithm for simplifying a set of linear inequalities

4 Answers4

Linked