10
$\begingroup$

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.

$\endgroup$

2 Answers 2

11
$\begingroup$

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

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

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}

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Nov 14, 2019 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.