Can we express max constraint as a linear constraint?

Question

I have a mathematical program with a constraint involving a maximum function. More specifically, the constraint is: $y = \max\{a_i x_i:1 \leq i \leq n\}$ where $a_i$ are constants and $x_i$ are binary variables. Can we express this constraint as a linear constraint?

Answer 1

First note that because your $x_{i}$ are binary variables you aren't really in the world of linear programming any more. Rather, this problem is a mixed integer linear programming problem (MILP).

Depending on your other constraints and objective, this may be doable by simply minimizing $y$ in the objective and enforcing the constraints:

$y \geq a_{i}x_{i}$ for $i=1, 2, \ldots, n$.

More generally, you can do this as follows.

I'm going to assume that the constants $a_{i}$ are positive. If not, the same general approach can handle the case where some $a_{i} \leq 0$.

I'll also assume that the coefficients have been sorted so that $a_{1} \geq a_{2} \geq \ldots \geq a_{n}$. This is just to simplify the notation- you can keep them in the original order if you're willing to keep track of the subscripts in writing the constraints that are given below.

Add binary variables $u_{i}$, $i=1, 2, \ldots, n$. Add the constraint

$\sum_{i=1}^{n} u_{i}=1$

This ensures that exactly one of the $u_{i}$ is 1. We will arrange things so that if $u_{k}=1$, then $k$ is the index of the $x$ variable that corresponds to the maximum of $a_{i}x_{i}$.

Next, add the constraints

$\sum_{i=1}^{k} x_{i} \leq n \sum_{i=1}^{k} u_{k} \;\; $, for $k=1, 2, \ldots, n$.

This ensures that if $u_{1}=u_{2}=\ldots=u_{k}=0$, then $x_{i}=0$ for $i=1, 2, \ldots k$.

Next, add the constraints

$(1-x_{i}) + u_{i} \leq 1$, for $i=1, 2, \ldots, n$

This ensures that if $u_{k}=1$, then $x_{k}=1$.

The combined effect of the above constraints is that if $u_{k}=1$, then $k$ is the index of the first $x_{i}$ variable that is 1.

Finally, add the constraint

$y=\sum_{i=1}^{n} a_{i}u_{i}$.