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
$\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$
  • $\begingroup$ That is much more simple. Thank you. $\endgroup$ – JBL Mar 30 at 1:21

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.