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

Reset to default
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$ Commented 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.