8
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice. ............ $\endgroup$
    – Mark L. Stone
    Dec 8 '20 at 2:56
6
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! Do you know if there is a "presolve" function in an open-source solver? Alternatively, are there published algorithms for presolve? $\endgroup$
    – Erel Segal-Halevi
    Dec 8 '20 at 9:42
  • 1
    $\begingroup$ Have a look into SCIP and publications from its developers. $\endgroup$
    – ktnr
    Dec 8 '20 at 11:54
  • $\begingroup$ 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 ampl.com/REFS/pripre.pdf $\endgroup$
    – Mark L. Stone
    Dec 8 '20 at 21:04
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.