Linearize $\max x_i\ge1$

Question

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?

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}