Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

I have a MIP minimization problem where I have a maximization in the constraints:

$$\max(c_1x_2,\, c_2x_2,\, \ldots,\, c_nx_n) \geq q$$

Where:

• $$c_n$$ constants
• $$x_n$$ binary variables
• $$q$$ constant

$$x_n$$ is not part of the objective function. How can I linearize this?

The first step to solve this would be to create a new variable $$z$$ representing the the maximum value. Further I think a Big M should be used. But what would become the constraints?

I found an option that almost does this but it is for two variables instead of $$n$$. For example $$\max(x,y)$$.

Furthermore, this problem is similar but doesn't cover the problem exactly.

2 Answers

You can do this with no new variables. Let $$S=\{k:c_k \ge q\}$$ and add the constraint $$\sum_{k\in S}x_k \ge 1$$.

• Thanks, I selected this as the better answer since I think this method is more efficient. Claudio Contardo's answer works aswell.
– Tim
Nov 15 '19 at 9:12
• Neat and simple, wonderful! Nov 15 '19 at 21:30

Assuming that the $$c_i$$ and $$q$$ are all positive you may add one binary variable $$y_i$$ for every $$i=1,\cdots,n$$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\geq 1\end{align}

• By the way, this is the same big-M approach as in the second linked post. Explicitly: $q - c_i x_i \le M(1-y_i)$, with $M=q$, simplifies to this. Nov 14 '19 at 15:28