Max and Min Functions in a MIP

Previously I wrote about how to work the "positive part" function ($y^+=\max(y,0)$) into a mixed integer programming model. More general uses of the $\max$ and $\min$ functions are really just an extension of this, but the extension may not be entirely obvious. In this post I'll explain how to set $z=\max(x,y)$ in a MIP model, where $x$, $y$ and $z$ are all variables. If the model was in fact a linear program before introducing the $\max$ or $\min$ function, it may remain an LP, or it may become a MIP, depending on exactly what you are doing.  I'll use the $\max$ function for explanatory purposes; the necessary tweaks to deal with the $\min$ function are left to the reader as an exercise.

Let's start with the obvious part: if $z=\max(x,y)$ then $$z\ge x$$ and $$z \ge y.$$In fact, adding those two constraints will be sufficient if the nature of the model ensures that the smallest feasible value of $z$ will always be chosen  Typically this means that (a) $z$ has a positive coefficient in an objective function being minimized, or a negative coefficient in an objective function being maximized, and (b) $z$ does not connect to other variables, through constraints, in a way that might allow an inflated value of $z$ to cause other variables to change enough that their improved objective contribution would more than pay for the damage done by inflating $z$.

There are also occasional cases where inflation of $z$ is not actually a concern: you need $z$ to be at least as big as both $x$ and $y$ (which the constraints ensure), but a larger than necessary value of $z$ will not affect the objective function or the values of other variables, and can be corrected manually once a solution is found.

The (slightly) tricky case is when you cannot be sure that the "pressure" of the  objective function will prevent inflated values of $z$ from occurring, and you really do need the value of $z$ to be correct.  To handle this case, we will need finite bounds for $x$ and $y$, so from here on I will assume that $L_x \le x \le U_x$ and $L_y \le y \le U_y$.  We have to introduce a new binary variable $w$, which will switch values depending on whether $x$ or $y$ is the larger of the two. In addition to the two previous constraints, we add the following:$$z \le x + (U_y - L_x)w$$and$$z \le y + (U_x-L_y)(1-w).$$The combined effect of the constraints is that $w=0\implies z=x\ge y$ and $w=1\implies z=y\ge x$.