🚀 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.