🚀 go-pugleaf

In article <batra.722077145@beagle>, batra@boulder.Colorado.EDU (sajeev batra) writes:
|> hi,
|> 
|> I have a large set of  linear inequalities (with about a 20 unknowns)
|> and I am about to use linear programming to solve for them.
|> Is there an algorithm that will tell me that my set is consistent or
|> inconsistent?  

Finding out whether a set of inequalities is consistent is on average
about half the work of solving the entire LP.  Unless there is some special
characteristic of your model that allows a priori analysis, there are no simple shortcuts that will give you what you want.  One proves a set is consistent
by finding a feasible solution;  one proves it's inconsistent by showing that
no feasible solution exists.  In either case an LP algorithm (probably the Simplex method) is your best bet.

|> Also, I need to know specifically which inequalities
|> contradict each other.  How do I go about doing this?  Any suggestions?

This question really is not as well-posed as you may think.  If a group
of inequalities is inconsistent (infeasible), there may be many ways of
removing a few to give a feasible set.  It's not likely you can point at
one or two and say "those are the culprits". One technique that comes to 
mind is goal-programming.  There are several ways people implement this, 
but one of the simplest is to add to each row an extra slack variable that
has a huge but meaningful cost of violating that constraint.  The model
is now feasible, since at a large cost the solver can just put in the new
slacks.  If the costs you assign are physically meaningful, then the
Simplex method will find the least costly way to violate as few constraints
as possible.

There is a recognized expert in the field of LP, Fred Glover, who is at
the University of Colorado at Boulder.  You may find it beneficial to
try to talk over your ideas with him.

- John Gregory
  Applications Dept.
  Cray Research, Inc.

In article <batra.722077145@beagle> batra@boulder.Colorado.EDU (sajeev batra) writes:
>hi,
>
>I have a large set of  linear inequalities (with about a 20 unknowns)
>and I am about to use linear programming to solve for them.
>Is there an algorithm that will tell me that my set is consistent or
>inconsistent?  Also, I need to know specifically which inequalities
>contradict each other.  How do I go about doing this?  Any suggestions?
>Please post or email.
>
>Thank YoO,
>sajeev
>batra@cs.colorado.edu
>

Phase I of the simplex method tells you which inequalities are inconsistent
with the system. Assume that you have a system of the form:
A x = b, b >=0
  x >= 0
(Your system can be transformed into this format easily)
Now add artificial variables to the previous system:
A x + y = b
  x,  y >= 0
Note that y=b >=0 is a solution to the previous system. This is your starting
solution. Minimize y1+y2+... If the solution is y1=y2=...=0 then the previous
system (Ax=b, x>=0) has a solution. Otherwise, any constraint with yi<>0 is
incosistent with the system.
-Samer

jwg@sparcman.cray.com (John Gregory) writes:
>|> 
>|> I have a large set of  linear inequalities (with about a 20 unknowns)
>|> and I am about to use linear programming to solve for them.


>|> Is there an algorithm that will tell me that my set is consistent or
>|> inconsistent?  

[...]
>This question really is not as well-posed as you may think.  If a group
>of inequalities is inconsistent (infeasible), there may be many ways of
>removing a few to give a feasible set.  It's not likely you can point at
>one or two and say "those are the culprits". 

Notice that the problem of finding a MINIMUM number of inequalities to remove in
order to restore feasibility is NP-complete.

-- 
| Fabio Schoen (assoc .prof. of Op.Res.)        e-mail:                     |
| Dipartimento di Scienze della Informazione    schoen@ghost.dsi.unimi.it   |
| via Comelico 39/41 - I20135 Milano ITALY                                  |
| fax: +39 (2) 55006.276 or 373                 Tel: +39 (2) 55006.319      |

I'd like to thank everyone who responded to my questions.  Thank you.
A number of people asked me for references and I did receive a couple.
I have not read thru them, but here are the two that I received :

1) 

"Fourier - Motzkin Elimination and Dual" , by George Dantzig and 
Curtis Eaves, Journal of Combinatorial Theory (A) 14, 288 -297 (1973). 

2)

"Locating Minimal Infeasible Constraint Sets in Linear Programs", 
by John Chinneck and Erik Dranieks, Spring 1991 ORSA Journal on 
Computing



Sajeev Batra
univ of colorado @ boulder