"No two values are the same" constraint in linear programming

Question

I have the following linear program.

$$\begin{array}{ll} \text{maximize} & x_1 + 2 x_2 + 3 x_3\\ \text{subject to} & x_1 + x_2 - x_3 = 1\\ & -2 x_1 + x_2 + 2 x_3 \geq -5\\ & x_1 - x_2 \leq 4\\ & x_2 + x_3 \leq 5\\ & x_1, x_2, x_3 > 0\\ & \color{gray}{\text{No two values are the same}}\end{array}$$

The problem I am facing is that I need to formulate the requirement that "no two values are the same" in a linear equation so that I can apply the Simplex method. I need to convert

$$ (x_1 \neq x_2) \wedge (x_2 \neq x_3) \wedge (x_1 \neq x_3) $$

into one or more linear constraints, but I don't know how. Please help. Thanks.

Update-1: I noticed a similar question at: How can not-equals be expressed as an inequality for a linear programming model

Answer 1

Assuming it's not integer programming, everything is continuous so the "probability" that the optimal solution has two values the same is $0$. Even if it does, you could add or subtract any $\epsilon>0$ from one value to make them unequal.

Otherwise you would need to split it into six linear programs with conditions $x_1<x_2<x_3$ and permutations, because $x_1\neq x_2$ isn't convex.

Answer 2

not equal is nonconvex and cannot be expressed using linear programming but requires a combinatorial approach, i.e. effectively in your case mixed-integer linear programming

What's worse though is that not equal in continuous variables really isn't well-posed, just as your strict positivity requirement is ill-posed. As a trivial example, consider minimize $|x-y|$ subject to $x\neq y$. Obviously no minimizer as you can make the optimal value arbitrarily small, but $0$ is not feasible.