How to linearize a constraint with a maximum or minimum in the right-hand-side?

Question

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

Answer 1

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