16
$\begingroup$

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)$$

$\endgroup$
4
  • 1
    $\begingroup$ are the constraints both active? Or do you want to have them independently? $\endgroup$ Jun 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$ Jun 1, 2019 at 14:16
  • $\begingroup$ Oops, sorry I misunderstood the original question! $\endgroup$ Jun 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$ Jun 2, 2019 at 11:54

1 Answer 1

12
$\begingroup$

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$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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