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.
Best Answer
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.