# How can not-equals be expressed as an inequality for a linear programming model

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?

• 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

If you want $x_1\neq x_2$, you can linearize $|x_1-x_2|\ge \varepsilon$, for example by introducing a boolean variable $y=1$ if and only if $x_1-x_2\ge \varepsilon$, and by imposing:

$$x_1-x_2\le -\varepsilon +My\quad \mbox{and}\quad x_1-x_2\ge \varepsilon-(1-y)M$$

Note: $\varepsilon$ is a "very small" constant close to zero and $M$ a very large integer.

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.

As you have seen, a "not equals" will mean that you have an "or" constraint in your linear program.

X <> Y => X > Y OR Y > X


Therefore, problem is no longer linear since you have two feasible regions/convex hulls.

To solve this, you can always solve one problem assuming

X < Y


And solve a second problem assuming

X > Y


Then compare the results to give your answer. It is likely that one of those assumptions will make the problem infeasible anyway.

Hope this helped!

• This doesn't really answer the question. He knows that X<Y or X>Y, the question was about the "or" part of that statement. – KSmarts Feb 6 '15 at 18:38

For integers, one can add a new 0-1 variable $$a$$ and an integer constant (sufficiently large) $$m$$ then use $$x-y+ma \geqslant 1$$ $$x-y +ma\leqslant m-1$$ to encode the relationship $x\neq y$.

I just realise that Kuifje's answer may be bettter.