11
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Kevin Dalmeijer
    Aug 20, 2019 at 8:29
  • 1
    $\begingroup$ 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 $\endgroup$
    – ephemeral
    Aug 20, 2019 at 10:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kevin Dalmeijer
    Aug 20, 2019 at 10:58

1 Answer 1

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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