MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: How to solve system of inequalities?

  • To: mathgroup at
  • Subject: [mg1065] Re: How to solve system of inequalities?
  • From: rubin at (Paul A. Rubin)
  • Date: Fri, 12 May 1995 16:10:54 -0400
  • Organization: Michigan State University

In article <3oker8$jh7 at>,
   jeff at wrote:
->Hi.  I have a system of linear inequlities specified symbolically.
->I want to test whether they are consistent.  (i.e. whether the
->solution region is non-empty).  I don't see how to do this and
->it is not covered in Wolfram's book.
->For example, I can surely type
->	In[1] 1<0
->and get back the expected
->	Out[1] False
->But if I enter
->	In[2] y<x && x<y
->I get back the unhelpful
->	Out[2] y < x && x < y
->Apparently Mathematica cannot deduce that this is impossible.
->Is there any way to get Mathematica to tell me when a series of
->inequalities is logically consistent?  The workaround I tried
->was to use ConstrainedMin which returns an error when the 
->Constraint inequalities have empty solution region.  The problem
->is that I need to enforce the inequalities to be strict and 
->Constrained seems to be willing to assume weak inequalites when
->necessary.  For example
->	In[3] ConstrainedMin[x,{x<y,y<x},{x,y}]
->	Out[3] {0, {x->0, y->0}}
->which is not what I wanted.
->There has got to be a simple way to do this, right?

I think you're on the right track in using ConstrainedMin, although you 
need to be careful:  ConstrainedMin assumes that all variables are 
restricted to being nonnegative.  If that's not true in your problem, you 
can work around it in one of two ways:  write every variable x as a 
difference x1-x2 of two new nonnegative variables; or add a single 
new nonnegative variable z, and replace every existing variable x with the 
difference x -> x1-z, where x1 is a new nonnegative variable.  The former 
approach doubles the number of variables, the latter adds just one to the 
variable count, and they are equally valid.

Now to the question of strict inequalities.  I don't think you'll get a 
definitive answer, but you can try the following:

Step 1:  If necessary, change variables so that all variables are 
nonnegative, and (for convenience) move terms around so that all variables 
appear on the left side of each constraint, the right side containing only 
a number.

Step 2:  Add/subtract a new nonnegative "artificial" variable to each 
inequality, so that if the original inequality is violated, the artificial 
variable soaks up the violation.  Thus
    blah blah blah <= number
    blah blah blah - u <= number
(same for strict <) and
    blah blah blah >= number
    blah blah blah + v >= number
(same for strict >), where u and v are the new artificial variables.  You 
add one artificial variable per inequality.

Step 3:  Convert strict inequalities to weak inequalities by perturbing the 
right hand side by a "small" amount (but not so small that the perturbation 
is below the accuracy threshold of the number).  Thus
    blah blah blah < number
    blah blah blah <= number*(1-epsilon)
    blah blah blah > number
    blah blah blah >= number*(1+epsilon)
where epsilon is a small positive number.  If the right hand side is zero, 
subtract or add epsilon, rather than multiplying as above.  Make sure you 
don't pick epsilon too small; you'll know it's too small if
    number*(1-epsilon) >= number
    number*(1+epsilon) <= number
evaluates to True.

Step 4:  Apply ConstrainedMin, using the sum of all artificial variables as 
the objective function, the modified inequalities as constraints, and the 
Join of the original variable list and the list of artificials as the 
variables.  If you get a zero objective value, the modified inequalities 
are consistent, which implies the original ones are.  If you get a nonzero 
objective value, the modified inequalities are inconsistent, which means 
that EITHER the original inequalities are inconsistent OR the original 
inequalities are (barely) consistent and you chose epsilon too large.  
(Sorry, it's not foolproof, but I doubt a foolproof method exists.)

Good luck.


* Paul A. Rubin                                  Phone: (517) 432-3509   *
* Department of Management                       Fax:   (517) 432-1111   *
* Eli Broad Graduate School of Management        Net:   RUBIN at MSU.EDU    *
* Michigan State University                                              *
* East Lansing, MI  48824-1122  (USA)                                    *
Mathematicians are like Frenchmen:  whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different.                                    J. W. v. GOETHE

  • Prev by Date: Optica?
  • Next by Date: Re: Integrate bug and workaround
  • Previous by thread: Re: Optica?
  • Next by thread: Re: How to solve system of inequalities?