1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @Rodrigo de Azevedo - Great job, its more clear this way. $\endgroup$ – NoChance Feb 3 '18 at 7:54
  • $\begingroup$ Have you tried solving the linear program without the "no two values are the same" constraint? $\endgroup$ – Rodrigo de Azevedo Feb 3 '18 at 8:06
  • $\begingroup$ @RodrigodeAzevedo, yes I did. In fact this is an example from a LP Calculator and the feasible solution is: 4.6667, 0.6667, 4.3333. No 2 values are equal here, but I wanted to know how express the constraint. $\endgroup$ – NoChance Feb 3 '18 at 9:52
  • 1
    $\begingroup$ You may want to take a look at chapter 5 of Decision Procedures. Some slides are available here. $\endgroup$ – Rodrigo de Azevedo Feb 3 '18 at 11:09
  • 1
    $\begingroup$ Precisely. On real-word problems with continuous variables, not equal really does not make sense, but you would have some quantization involved, such as $|x-y|\geq L$, and that model is easily MILP-representable, as discussed in the question you linked to. $\endgroup$ – Johan Löfberg Feb 4 '18 at 6:22
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ lmao I didn't even notice that $\endgroup$ – Akababa Feb 3 '18 at 8:37
  • $\begingroup$ Assuming the polytope has nonzero volume, every neighborhood of the vertex intersects the polytope with positive measure. On the other hand the planes $x_1=x_2$ etc have 0 measure, so just take a point in the neighborhood. $\endgroup$ – Akababa Feb 3 '18 at 9:13
  • $\begingroup$ I would assume that the, in general, the probability of all variables to be of the same value is not zero. However, breaking the problem in all possible combinations is theoretically valid. If we add the assumption that $x$ values are all integers, could we find a way to solve it? $\endgroup$ – NoChance Feb 3 '18 at 9:42
  • $\begingroup$ Well the planes $x_1=x_2$, etc. actually divide the $\mathbb{Z^3}$ into 6 regions, so in general you can't solve it with one linear program unless your polytope lies in one of them (i.e. you can deduce the ordering of $x_1,x_2,x_3$ from the other inequalities). $\endgroup$ – Akababa Feb 3 '18 at 9:47
  • $\begingroup$ Well you can always split it into 6 linear programs. The "perturbation" argument is only an intuitive explanation of why you can find solutions arbitrarily close to the optimum. $\endgroup$ – Akababa Feb 3 '18 at 10:10
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.