[Math] Linear Programming: Breaking Variables Product

integer programminglinear programming

Given two sets of binary variables $x_{i…N} \in X$ and $y_{i…M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables?

$\alpha\sum_i^N x_i = \alpha\sum_j^M y_j$

In practice what I want is to enforce that $\alpha\sum_i^Nx_i=\alpha\sum_j^M y_j$ or $\alpha\sum_i^N x_i=0$

Best Answer

Each $\alpha x_i$ term can be reformulated using a continuous variable $\beta_i$ and three constraints as follows:

$\beta_i \leq \alpha \\ \beta_i \leq x_i \\ \beta_i \geq \alpha + x_i - 1$

Reformulate the $\alpha y_j$ terms the same way using another continuous variable, say $\gamma_j$.

Then, use the big-M method from integer programming to handle the "either-or" constraint that you want to enforce, using a binary variable $\delta$, a sufficiently large constant $M$, and two constraints as follows:

$\sum_j \gamma_j - M\delta \leq \sum_i \beta_i \leq \sum_j \gamma_j + M\delta \\ \sum_i \beta_i \leq M(1-\delta)$