# Linearize $\max x_i\ge1$

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?

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}
• 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. – RobPratt Feb 26 at 16:54