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

Question

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.

Answer 1

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

Answer 2

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}