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$
11
  • 1
    $\begingroup$ Have you tried solving the linear program without the "no two values are the same" constraint? $\endgroup$ Commented Feb 3, 2018 at 8:06
  • 1
    $\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$ Commented Feb 3, 2018 at 9:52
  • 2
    $\begingroup$ You may want to take a look at chapter 5 of Decision Procedures. Some slides are available here. $\endgroup$ Commented Feb 3, 2018 at 11:09
  • 2
    $\begingroup$ exactly,you're doing mixed-integer programming as the decision variables definitely aren't continuous. I'm asking about a relevant LP problem $\endgroup$ Commented Feb 3, 2018 at 18:40
  • 2
    $\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$ Commented Feb 4, 2018 at 6:22

2 Answers 2

Reset to default
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$
3
$\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$
6
  • $\begingroup$ lmao I didn't even notice that $\endgroup$ Commented Feb 3, 2018 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$ Commented Feb 3, 2018 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$ Commented Feb 3, 2018 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$ Commented Feb 3, 2018 at 9:47
  • 1
    $\begingroup$ your suggestion about $\epsilon>0$ is valid for the non-integer case. See my question updates. Thank you. $\endgroup$ Commented Feb 3, 2018 at 10:25

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.