4
$\begingroup$

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$

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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