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}
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Consider the only two possible cases:
- 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)$.