1
$\begingroup$

I am trying to find a way to implement an OR equality constraint in a Binary Integer Program. For example, say I want to add the following logical condition to the program:

$$x_1+x_2+x_3+x_4+x_5 = 1\; \text{OR}\; x_1+x_2+x_3+x_4+x_5 = 3$$

$$\textbf{x}\in \mathbb{B}^5$$

The big-M method does not seem to work here because we are dealing with equalities rather than inequalities. I also have not seen any literature on this after a search. My only idea is to come up with all the possible partitions of the five variables and individually assign constraints as according. For example...

$$\text{IF } x_1 \geq 1 \rightarrow x_{2,...,5} \leq 0 \text{ OR } x_1 \geq 1 \rightarrow x_2 \geq1, x_3 \geq 1, x_4 \leq 0, x_5 \leq 0 \text{ OR } ...$$

And then use the big-M method. But this is obviously very tedious and the constraints grow exponentially for such a simple OR statement. Do you have any ideas/hints on how to approach this? Thanks

$\endgroup$

2 Answers 2

2
$\begingroup$

You can do this by setting two more binary variables $y_1,y_2$ in a way: $$x_1+x_2+x_3+x_4+x_5=y_1+3y_2$$ where $$y_1+y_2=1$$

$\endgroup$
1
  • $\begingroup$ That is much more simple. Thank you. $\endgroup$
    – Mason
    Mar 30, 2019 at 1:21
0
$\begingroup$

You can do it with one additional binary variable $y$: $$\sum_{i=1}^5 x_i = 1 + 2y.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .