Skip to main content
added 477 characters in body
Source Link
RobPratt
  • 33.1k
  • 2
  • 47
  • 89

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

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

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

Source Link
RobPratt
  • 33.1k
  • 2
  • 47
  • 89

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