Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.