4
$\begingroup$

I'm trying to linearize this optimization problem ($S_j$ is a subset of variables): \begin{align}\min&\quad\sum_{x_i \in X} x_i\\\text{s.t.}&\quad\max_{i \in S_j}x_i\geq 1\quad\forall S_j\\&\quad0 \le x_i \le 1\end{align}

Unfortunately, I have no idea to linearize my maximum constraint. The following naïve constraint is not good enough: $\sum_{i \in S} x_i \geq 1$.

Do you have any better ideas than mine?

$\endgroup$
8
$\begingroup$

For each $j$, you want to enforce $x_i \ge 1$ for at least one $i\in S_j$. Introduce binary variable $y_i$ to indicate whether $x_i=1$, and impose linear constraints \begin{align} \sum_{i \in S_j} y_i &\ge 1 &&\text{for all $j$} \\ y_i &\le x_i &&\text{for all $i$} \\ \end{align}

$\endgroup$
2
  • $\begingroup$ Thank you for your quick answer. However, I wish I could linearize my linear program using only floating variables (because existing variables are not integer). If I can't, maybe there exists a better relaxation of my max constraint which is better than my naïve sum constraint? $\endgroup$
    – Mithous
    Feb 26 at 16:48
  • 9
    $\begingroup$ Your maximum constraint is not convex so cannot be linearized without introducing integer variables. Consider even the simplest example $\max(x_1,x_2) \ge 1$, which yields an L-shaped feasible region. Your linear relaxation $x_1+x_2 \ge 1$ is best possible. $\endgroup$
    – RobPratt
    Feb 26 at 16:54

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.