13
$\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$
  • 1
    $\begingroup$ are the constraints both active? Or do you want to have them independently? $\endgroup$ – independentvariable Jun 1 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 Broek Jun 1 at 14:16
  • $\begingroup$ Oops, sorry I misunderstood the original question! $\endgroup$ – LarrySnyder610 Jun 2 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 Broek Jun 2 at 11:54
9
$\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, privacy policy and cookie policy

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