# Linear Programming: Breaking Variables Product

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^Nx_i = \alpha\sum_j^Ny_j$

In practice what I want is to enforce that $\alpha\sum_i^Nx_i=\alpha\sum_j^Ny_j$ or $\alpha\sum_i^Nx_i=0$

-

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

-

Your logical condition is equivalent to

$$\alpha=0 \vee\sum_{i=1}^N x_i = 0 \vee \sum_{i=1}^N (x_i-y_i)=0.$$

This is equivalent to

$$(1-\alpha) + \delta_x + (\delta^{+} + \delta^-1) \geq 1\\ 1-\delta^+\leq \sum_{i=1}^N x_i\\ \sum_{i=1}^N (x_i - y_i) -1 \geq -(N+1)\delta^-\\ \sum_{i=1}^N (x_i - y_i) \geq -N(1-\delta^+)\\ (N+1)\delta^+ \geq \sum_{i=1}^N (x_i - y_i) +1\\ N(1-\delta^-) \geq \sum_{i=1}^N (x_i - y_i) \\$$

where $\delta^+,\delta^-,\delta_x\in\{0,1\}.$

-