5
$\begingroup$

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 &&\text{for all $i$} \tag{3}\\ \end{align}

$\endgroup$
5
$\begingroup$

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)$.

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