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.