2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is this a constraint or an objective? Usually in LP you see max/min in the objective. $\endgroup$ – Godric Seer May 1 '14 at 14:27
4
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.