Max/Min Bounds

Motivated by a recent question on OR-Exchange, this post expands on a previous post about constraints that set a variable equal to the maximum or minimum of other variables in a mathematical program. Here I'll deal with inequality bounds (and with more than two variables involved in the maximum/minimum).

The setting is a mathematical programming model containing variables $x_1,\dots,x_n$ and $y$, where you want to bound $y$ either above or below by either $\max_{i=1,\dots,n} x_i$ or $\min_{i=1,\dots,n}x_i$. Let's dispense with the easy cases first. Since $$\begin{eqnarray*} y\ge\max_{i=1,\dots,n}x_{i} & \iff & y\ge x_{i}\forall i=1,\dots,n\\ y\le\min_{i=1,\dots,n}x_{i} & \iff & y\le x_{i}\forall i=1,\dots,n \end{eqnarray*}$$ those two cases are handled by expanding one nonlinear inequality into $n$ linear inequalities, with no requirement that the variables be bound and no introduction of integer variables.

Now let's consider the case $y\le\max_{i=1,\dots,n}x_i$. (The case $y\ge\min_{i=1,\dots,n}x_i$ is symmetric and left to the reader as an exercise.) The key to our approach is that $$y\le\max_{i=1,\dots,n}x_i\iff \exists i \ni y\le x_i.$$ To handle this case, we need a priori bounds on the $x$ variables, say $L_i\le x_i\le U_i\ \ \forall i$. Let $\bar{U}=\max_{i=1,\dots,n}U_i$, and note that if the constraint $y\le\max_{i=1,\dots,n}x_i$ is to hold, then clearly $y\le\bar{U}$.

We introduce binary variables $\delta_1,\dots,\delta_n$ and the constraint $$\delta_1+\cdots+\delta_n=1.$$ Depending on the solver being used, it may be beneficial to specify to the solver that the $\delta$ variables form a type 1 special ordered set (SOS1). Now add the following $n$ constraints: $$y\le x_i + (\bar{U}-L_i)(1-\delta_i)\ \ \forall i=1,\dots,n.$$ If $\delta_i=0$, the right hand side becomes $x_i+\bar{U}-L_i\ge\bar{U}$, and the constraint is vacuous. For the one index where $\delta_i=1$, the constraint reduces to $y\le x_i$, which is all we need.

Addendum 1: It belatedly occurred to me that it would be equally valid to replace $\delta_1+\cdots+\delta_n=1$ with $\delta_1+\cdots+\delta_n\ge 1$ (in which case it is no longer an SOS1 constraint). Requiring $y\le \max_{i=1,\dots,n} x_i$ is equivalent to saying $y\le x_1$ OR $y\le x_2$ OR ... OR $y\le x_n$, with the ors being inclusive. I have no idea whether this second version is more or less efficient computationally than using the SOS1 constraint.

Addendum 2: Erwin Kalvelagen posted some alternative, possibly tighter, formulations on his blog.