I have a very large number (670 billion) of systems of inequalities of the form:


$C\_1 - C\_2 < C\_4 - C\_3 \wedge C\_3 - C\_2 < C\_5 - C\_3 \wedge ...$


where the $C\_i > 0$. Ie. each system of inequalities consists of the comparisons of differences between positive real numbers which must all be true at the same time.


Now I want to find the subset of systems which are consistent, ie. there exists a choice of $C\_i$ such that all inequalities are satisfied.


Given the the large number of systems this method would have to be automated. Therefore my question is:


Is there an algorithm to decide whether a system of inequalities of the form described above is consistent?



Consistency of systems of inequalities involving only differences
Hellooooooooo !!!


This could be done by a linear solver... to some extent ! A linear program accepts a set of constraints of the form (linear function >= 0), and tells you whether there exists an assignment of values to your variables such that all the constraints are satisfied.


The "only difference" between your problem and what a LP solver can do is that the LP solver cannot understand strict inequalities. Hence you would have to add linear constraints of the form variable >= some\_very\_small\_value.


I think these answers could still be useful to you. Theoretically, you can even obtain certificated of infeasibility (a set of ocnflicting constraints), but it is harder to obtain in practice.


If you want to give it a try, you should look for Linear Program solvers like GLPK (free), CPLEX(proprietary), Coin (free), Gurobi (Proprietary). These programs accept as input a .mps or .lp file describing your set of constraints (I expect this to appear in the documentation of each of these solvers).


You can als do this computation through Sage (<http://www.sagemath.org>), and by looking at this short tutorial on LP (for graph applications !)
<http://steinertriples.fr/ncohen/tut/LP/>


Good luck ! ;-)


Nathann


