Welcome to MathOverflow

Question

4

1

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?

flag	asked Mar 29 2012 at 8:47 derfred 43●2

	That's a lot of systems -- if each takes a second to determine consistency than you will need 21 thousand years of machine time. – J.J. Green Mar 29 2012 at 11:13
	how many variables are there? – Brendan McKay Mar 29 2012 at 11:39
	@JJ yes it's a lot of systems. But they are not actually unique as many of them are related by symmetry, but I have not worked out the actual symmetry. Furthermore for my problem I only need one example of a consistent system. – derfred Mar 29 2012 at 11:44
	@Brendan, there are 8 variables in total – derfred Mar 29 2012 at 11:45
	Sorry, but I don't get it. If there are only 8 variables, only a small number (less than $4^8=65536$) of different inequalities of the form $C_i-C_j<C_k-C_\ell$ can exist. So how can you have 670 billion? – Brendan McKay Mar 29 2012 at 12:44

show 3 more comments

Nathann Cohen · Accepted Answer · 2012-03-29 10:08:50Z UTC

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

Consistency of systems of inequalities involving only differences

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.