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

Solution 1:

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.

Solution 2:

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.