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

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?

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)

• Interesting approach :) If I am not mistaken you should replace $x_p$ by $b_p$ to match the problem definition. Also, I would guess that you do not explicitly need the $y_p$ variables to be declared as binary, just being in the interval {0,1} is probably enough, no? Finally do you really need the $b_p \leq y_p$ constraints? – Renaud M. Jun 21 '19 at 17:33
• Thanks @RenaudM. It's true. I'll add these comments to the answer. – Borelian Jun 21 '19 at 17:45

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

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

• Actually if I take your example nothing prevents l from reaching 20. You state that x1=0.5 and x3=0.5 but there is nothing preventing x1 taking value 0 and x3 taking value 1, or am I missing something ? I agree with you that the RHS will not always necessarily be equal to $max_{p \in P}(b_p c_p)$, if there is no need in the optimal solution for l to reach this value, it can definitely be that the x values lead to a smaller value, but as far as I can tell this will be exactly as constraining as the non-linear formulation, no? – Renaud M. Jun 19 '19 at 21:02
• About your approach, something is unclear to me. $K \leq \frac{ b_p c_p}{\sum c_p}$ you add this for every $p \in P$, correct? Doesn’t this mean that K=0 if there exist $p \in P$ such that $b_p$ = 0? Which would lead to $l$ = 0 if one of the $b_p$ is null. – Renaud M. Jun 19 '19 at 21:06
• @RenaudM., you are right, I forgot to mention that the inequality is for those p in P that has b_{p}=1. There is also some constraint to chose only those p that has the binary variable equal to 1. – Oguz Toragay Jun 20 '19 at 2:02

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.

• I believe this formulation is correct (provided the introduced $x_p$ variables are not used elsewhere in the LP). Rob Pratt's formulation is also correct. The advantage of this one is that it does not require the introduction of extra binary variables. – Mark H Jun 20 '19 at 1:00
• @MarkH: You are correct that the $x_p$ variables should not be used elsewhere in the model, otherwise it might lead to cut out some feasible solution. I'll edit my answer to reflect that. – Renaud M. Jun 20 '19 at 9:45