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)$$
Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this communitySuppose 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)$$
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: