Suppose we have three variables, $x, y, z \in \mathbb R$. How can we linearize constraints with the following structure?
$$z \geq \min(x, y)$$ $$z \leq \max(x, y)$$
$\begingroup$
$\endgroup$
4
asked Jun 1, 2019 at 10:49
-
1$\begingroup$ are the constraints both active? Or do you want to have them independently? $\endgroup$– independentvariableJun 1, 2019 at 11:05
-
1$\begingroup$ I meant both constraint independently. However there is already an answer that considers them simultaneously. Tomorrow I'll adjust this question to be the version for both constraints simultaneously and I will make a new question that considers them independently. $\endgroup$– Michiel uit het BroekJun 1, 2019 at 14:16
-
$\begingroup$ Oops, sorry I misunderstood the original question! $\endgroup$– LarrySnyder610Jun 2, 2019 at 2:45
-
$\begingroup$ Currently, I am typing the question with both constraints independently, but are the answers to both versions not too similar to deserve a separate question? $\endgroup$– Michiel uit het BroekJun 2, 2019 at 11:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Basically the condition is saying, $z$ must be between $x$ and $y$, regardless of whether $x \le y$ or $y \le x$.
Here's a method that involves a new binary variable and a big-$M$.
Let $w$ a binary variable that equals 1 if $x < y$: $$\begin{align} y - x & \le Mw \\ x - y & \le M(1-w) \end{align}$$ So, if $x < y$ then $w$ must equal 1; if $x > y$ then $w$ must equal 0; and if $x=y$ then $w$ could be either.
Now add the following constraints: $$\begin{align} z & \ge y - Mw \\ z & \le x + Mw \\ z & \ge x - M(1-w) \\ z & \le y + M(1-w) \end{align}$$ In other words:
- If $x < y$ ($w=1$), then $z$ must be $\ge x$ and $\le y$
- If $x > y$ ($w=0$), then $z$ must be $\ge y$ and $\le x$
- If $x=y$, then we don't know what $w$ equals, but either way, the constraints amount to $z = x = y$.
answered Jun 1, 2019 at 11:23