Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.