9
$\begingroup$

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

$\endgroup$
0

1 Answer 1

9
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.