10

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.

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Tim
  • 205
  • 1
  • 6

2 Answers2

11

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

prubin
  • 39,078
  • 3
  • 37
  • 104
10

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}

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Claudio Contardo
  • 1,574
  • 6
  • 13
  • 2
    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. – RobPratt Nov 14 '19 at 15:28