# How can I strengthen a family of constraints in the presence of a clique constraint?

Suppose $$x_i$$ are binary variables, $$y_j$$ are arbitrary variables, $$a_j$$ and $$b$$ are constants, and I have the following linear constraints: \begin{align} x_i + \sum_j a_j y_j &\le b &&\text{for all i} \tag1\\ \sum_i x_i &\le 1 \tag2 \end{align} How can I replace $$(1)$$ with $$(3)$$? \begin{align} \sum_i x_i + \sum_j a_j y_j &\le b \tag{3}\\ \end{align}

• If $$x_i=0$$ for all $$i$$, then $$(1)$$ and $$(3)$$ both reduce to $$\sum_j a_j y_j \le b$$.
• If $$x_i=1$$ for some $$i$$, then $$(2)$$ implies that $$x_k=0$$ for all other $$k \not= i$$, and $$(1)$$ and $$(3)$$ both reduce to $$1+\sum_j a_j y_j \le b$$.
Alternatively, you can think of lifting $$x_i+\sum_j a_j y_j \le b$$ to $$\alpha_k x_k + x_i+\sum_j a_j y_j \le b$$ for some $$k \not= i$$. If $$x_k=0$$, then $$\alpha_k$$ can be anything. If $$x_k=1$$, then $$x_i=0$$ by $$(2)$$ and you want to find the largest $$\alpha_k$$ such that $$\alpha_k+\sum_j a_j y_j \le b$$ is valid. Constraint $$(1)$$ implies that you should take $$\alpha_k=1$$, yielding $$x_k + x_i+\sum_j a_j y_j \le b$$. Now repeat this argument to obtain $$(3)$$.