Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
$\delta_1, \delta_2, ..., \delta_k, W$ are binary variables and the constraint $δ_1 + δ_2 + \ldots + δ_k ≤ W$ holds.
Is it better to write $$\delta_1 + \delta_2 + \ldots +\delta_k \leq W$$ or \begin{gathered} \delta_1 \leq W \\ \delta_2 \leq W \\ ...\\ \delta_k \leq W \\ \end{gathered}
and why?
Since $W$ is a binary variable, it follows that $$ \sum_k \delta_k \le W \le 1 $$ And so you are in the presence of a clique constraint.
@RobPratt shows how to strengthen the second group of constraints in this case, yielding the first constraint.
A simple example : take $\delta_k = 0.9$ for every $k$. It is easy to see that such a solution is valid with the second group, but not with the first one. So the first one leads to a tighter relaxation.
