How to linearize $\min\{\max\{0,x\},y\}$ as constraint in MILP?

Question

I am formulating a MILP and one of the constraints is

$\min\{\max\{0,y-x+a\},b\} \leq c$.

with decision variables $x, y \geq 0$ and $a,b,c$ as constants.

How would I ideally introduce auxiliary variables and formulate constraints to get rid of the nonlinearity of the $\min$ and $\max$ functions?

Answer 1

Introduce two continuous variables $z$ and $w$, where $z$ will represent the outer $\min$ and $w$ will represent the inner $\max$. So far, we have: \begin{align} z &\le c \tag 1\\ z &= \min(w,b) \tag 2\\ w &= \max(0, y-x+a) \tag 3 \end{align} To linearize (2), we can enforce $z \le \min(w,b)$ with: \begin{align} z &\le w \tag{2a}\\ z &\le b \tag{2b} \end{align} But we also want to enforce $z \ge \min(w,b)$. Introduce binary variable $u$, where $u=0 \implies z \ge w$ and $u=1 \implies z \ge b$, which we can enforce with: \begin{align} z - w &\ge (b-\overline{w}) u \tag{2c} \\ z - b &\ge (\underline{z} - b) (1-u) \tag{2d} \end{align} Here, take $\underline{z} = \min(0,b)$ and $\overline{w} = \overline{y} - \underline{x} - a$, where $\underline{y} \le y \le \overline{y}$ and $\underline{x} \le x \le \overline{x}$.

To linearize (3), we can enforce $w \ge \max(0,y-x+a)$ with: \begin{align} w &\ge 0 \tag{3a}\\ w &\ge y-x+a \tag{3b} \end{align} But we also want to enforce $w \le \max(0,y-x+a)$. Introduce binary variable $v$, where $v=0 \implies w \le 0$ and $v=1 \implies w \le y-x+a$, which we can enforce with: \begin{align} w &\le \overline{w} v \tag{3c} \\ w-(y-x+a) &\le (-\underline{y} +\overline{x} - a) (1-v) \tag{3d} \end{align}

Answer 2

If $b\le c$, the constraint is satisfied by any $x$ and $y$ and you can drop it. If $b > c$, the constraint reduces to $\max\lbrace 0, y-x+a\rbrace \le c$. This is unsatisfiable if $c < 0$, so assume $c\ge 0$. The constraint now reduces to $y-x+a \le c$.