Skip to main content
3 of 4
deleted 4 characters in body
TheSimpliFire
  • 5.5k
  • 5
  • 23
  • 56

Linearize $\max c_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_{x_i \in S_j}x_i\geq 1\quad\forall S_j\\&\quad1 \geq x_i \geq 0\end{align}

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

Do you have any better ideas than mine?