Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have this linear programming model I'm building but one of the constraints needs to specify that the solution's basic variables need to all be different from one another. This is an integer linear program.

How can we rewrite, for example, this constraint: x1 <> x2
using strictly the inequality operators which LP constraints require?

An obvious first step is to rewrite it and begin to simplify the expression as follows.

(x1 <= x2) AND (x1 >= x2) :This says x1 = x2 using the inequality operators

NOT ( (x1 <= x2) AND (x1 >= x2) ) :Simply negate the above to get x1 <> x2

Now you might say I can stop here but that outer NOT is a problem. To write two separate constraints in an LP you have to get rid of that outer NOT operator. The AND operator is automatically implied to join all the constraints in an LP (ie., constraint A AND constraint B AND constraint C must all be satisfied in the feasible solutions.)

To get rid of the outer NOT operator we can use DeMorgan's Theorem but then we are stuck with an OR operator. We prefer AND operators to join our constraints. Here is DMT's effect on our expression:

NOT (x1 <= x2) OR NOT (x1 >= x2) :DMT

(x1 > x2) OR (x1 < x2) :Simplifying

This is now in the form

A OR B

which is nice except like I said that "OR" operator is a pain in the neck, since for our constraints we need something in the form

A AND B

How can a "not equals" inequality be transformed to be suitable for use in linear programs?

Is there such a transformation possible?

Thanks for reading.

share|improve this question
    
It is intutive it does not work, because polyhedrons are convex and closed, while not-equals correspond to non-convex open regions. –  shuhalo Feb 13 '13 at 12:11

1 Answer 1

Suppose $x_1,x_2$ could take only the three values $0,1,2$. Take the integer lattice and put a dot for each allowable combination. The relevant $3\times 3$ square will look like this ($1$ means dot, $0$ means no dot): $$\begin{align*} &011 \\ &101 \\ &110 \end{align*}$$ Notice the "no dot" in the middle. Now take your IP and extend it to an LP. The feasible region must be convex. But there is no convex region in $\mathbb{R}^2$ that contains the $1$s above but not the $0$ in the center, since the $0$ is in the convex hull of the $1$s.

share|improve this answer

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.