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

| improve this answer | |
$\endgroup$
  • $\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 '19 at 9:12
  • 2
    $\begingroup$ Neat and simple, wonderful! $\endgroup$ – Claudio Contardo Nov 15 '19 at 21:30
9
$\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}

| improve this answer | |
$\endgroup$
  • 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 '19 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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