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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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