Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 '12 at 11:13
    
how many variables are there? –  Brendan McKay Mar 29 '12 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 '12 at 11:44
    
@Brendan, there are 8 variables in total –  derfred Mar 29 '12 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 '12 at 12:44
show 3 more comments

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
sorry I forgot to add something : if you want to find out about these certificates, the keyword is "farkas certificate" –  Nathann Cohen Mar 29 '12 at 10:09
    
thanks. Ill give that a go. –  derfred Mar 29 '12 at 10:27
    
Since in this case, all inequalities are strict (or at least this seems to be the case, according what derfred wrote so far), one can actually solve this exactly by asking whether the polytope defined by the non-strict inequalities $c_i-c_j\leq c_k-c_\ell$ has empty interior or not (i.e. is full-dimensional). This is certainly doable, but it might be expensive if there are many inequalities in your systems... In fact, how large are your systems "on average"? –  Max Horn Mar 29 '12 at 16:42
    
Given any real solution $\{C_i\}$ of the strict inequalities, multiply by a large enough constant so that difference between the sides of each inequality exceeds 2, then round each variable to the nearest integer. Therefore it suffices to consider integer solutions of the non-strict inequalities $C_i-C_j\le C_k-C_\ell-1$. –  Brendan McKay Mar 29 '12 at 21:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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