How to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-side

Question

I have the following constraint that I'd like to linearize:

$P$ is a given set

$b_p \in \{0,1\} , \forall p \in P$ a binary variable associated with each element of $P$

$c_p \in \mathbb{R}^+$, a coefficient associated with each element of $P$

$l \in \mathbb{R}^+$ a linear variable

Now the constraint that I would like to linearize is the following:

$l \leq \max_{p \in P}(b_p c_p)$

Any suggestions?

Answer 1

An alternative approach to the correct answer of @RobPratt to avoid the "Big-M" constraints.

Assume that your indices in $P$ can be ordered by the values of $c_p$. Then you add binary variables $y_p \in \{0,1\}$ and the constraints $b_p\leq y_p$, $y_p \leq y_{p-1}$ and $y_p \leq \sum\limits_{k\geq p} b_p$ for all $p\in P$.

(Idea: $y_p=1$ if and only if there is a $b_k=1$ for some $k\geq p$)

Then, you can add constraints $$l \leq c_0 y_0 + (c_1-c_0) y_1 + \ldots + (c_{|P|}-c_{|P|-1})y_{|P|}$$

(Idea: if $b_p=1$ then $y_0=y_1=\cdots=y_{p}=1$ and this forces that $l\leq c_p$.)

If the indices of $P$ have another order, the indices in the constraints can be easily permuted to obtain an equivalent formulation.

EDIT: Variables $y_p$ don't need to be binary, just $y_p\in[0,1]$. Also, you don't neccesarily need constraints $b_p\leq y_p$. They are required to obtain an if-and-only-if in the first idea, but in the context of the problem, the implication $y_p=1 \Longrightarrow b_k=1$ for some $k\geq p$ is enough. (Thanks @RenaudM for these comments)

Answer 2

We want $\ell \le c_p b_p$ for at least one $p \in P$. Let $c_\max = \max\limits_{p \in P} c_p$. Then we have an upper bound $\ell \le c_\max$. Now introduce binary variable $y_p$ and linear "big-M" constraint $\ell - c_p b_p \le c_\max (1-y_p)$ for each $p \in P$. Finally, linear constraint $\sum\limits_{p \in P} y_p \ge 1$ forces at least one $y_p = 1$, which together with the big-M constraints yields $\ell \le c_p b_p$ for that $p$.

Answer 3

This is how I ended up doing it:

Let's introduce an extra linear variable

$x_p \in [0,1], \forall p \in P$ a continuous variable between 0 and 1

$x_p \leq b_p, \forall p \in P$

$\sum_{p \in P} x_p \leq 1$

now I can replace my original non-linear constraint with the following one:

$l \leq \sum_{p \in P}(x_p c_p)$

It should be noted that the $x_p$ variables should not be used elsewhere in the model.

Answer 4

I think your answer needs to be improved. Consider the following example and feasible answer to the constraints:

$P=\{1,2,3\}, \ \ b_p=\{1,0,1\} \ \ \text{and} \ \ c_p=\{10,20,20\}$

now $\ x_1=0.5, \ x_2=0, \ x_3=0.5$ then $\ l \leq (0.5 \times 10 +0.5 \times 20)=15$

which is not the answer that you expected from $\ l \leq \max_{p \in P}(b_p c_p) \ $ which should be in this example $l \leq20$.

$\textbf{My approach:}$

Define $K\leq \frac{b_p c_p}{\sum c_p} \ $ then maximize $K$ in your model by adding the multiplication of an appropriate coefficient and $K$ to the objective function and then add the following to the constraints:

$l \leq K.\sum_{p\in P} c_p$