11

How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that question, I asked specifically about the scenario where the variable on the left-hand sides is always the same.

For this question, I am interested in the more general case. For example, $$(x_1 \leq x_3) \textrm{ OR } (x_2 \leq x_3) \textrm{ OR } (x_1 \leq x_4),$$ in which the left-hand sides nor the right-hand sides are always the same.

A boolean OR of just two variables can be expressed by introducing an additional variable and modifying the constraints appropriately. But how can we model the general case described above?

LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
ephemeral
  • 897
  • 4
  • 12
  • Can we assume the following generic form: $x_1 \le x_2$ OR $x_3 \le x_4$ OR $\dots$ OR $x_{n-1} \le x_n$, with $x_1, \dots, x_n$ all binary? You can consider editing your question to add this if this is the case, or to add a general form that does work for you if not. – Kevin Dalmeijer Aug 20 '19 at 08:29
  • 1
    No, there maybe repetitions of variables, however the repetition is restricted only on the LHS or on the RHS, I have edited the example to include such a scenario @KevinDalmeijer – ephemeral Aug 20 '19 at 10:19
  • 1
    Thank you for the clarification. I also did an edit to make sure that your question is understood correctly. If you disagree, feel free to roll back my edit, or edit your question further. – Kevin Dalmeijer Aug 20 '19 at 10:58

1 Answers1

11

Let $P$ be the set of $(i,j)$ pairs. Here’s a derivation via conjunctive normal form: \begin{equation} \bigvee_{(i,j)\in P} \left(x_i \implies x_j\right) \\ \bigvee_{(i,j)\in P} \left(\neg x_i \vee x_j\right) \\ \sum_{(i,j)\in P} \left(1-x_i + x_j\right) \ge 1 \\ \sum_{(i,j)\in P} (x_i - x_j) \le |P| - 1 \end{equation} For your example, this yields $$2x_1+x_2 - 2x_3 - x_4 \le 2.$$

RobPratt
  • 32,006
  • 1
  • 44
  • 84