9

$\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?

Clement
  • 2,252
  • 7
  • 13

1 Answers1

9

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.

Kuifje
  • 13,324
  • 1
  • 23
  • 56