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?


1 Answer 1


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}

  • $\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
    Commented Feb 26, 2021 at 16:48
  • 10
    $\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
    Commented Feb 26, 2021 at 16:54

Your Answer

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

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