Skip to main content
2 of 3
edited title
LarrySnyder610
  • 13.2k
  • 3
  • 42
  • 106

Expressing an implication as ILP where each implication term comprises a chain of boolean ORs

Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this be expressed as an ILP? All variables are Boolean.

I have derived the following using CNF, however it turns out to be non-linear, can this be expressed in Linear Form?

Let us suppose $A = \{ a_1, a_2, a_3\}$ and $B = \{ b_1, b_2, b_3\}$. thus,

\begin{equation} \bigvee A \implies \bigvee B \\ \overline{(\bigvee A)} \bigvee (\bigvee B) \\ (\bigwedge_{a \in A} \overline a) \bigvee (\bigvee B) \\ (\bigwedge_{a \in A} (1-a)) \bigvee (\bigvee B) \\ (\prod_{a \in A} (1-a)) \bigvee (\sum_{b \in B} b) \\ (\prod_{a \in A} (1-a)) + (\sum_{b \in B} b) \geq 1 \end{equation}

Thus, thus leads to $(1-a_1)(1-a_2)(1-a_3) + b_1 + b_2 + b_3 \geq 1$, which essentially leads to a product of complements of the variables in A. Can this be expressed in terms of linear constraints?

ephemeral
  • 917
  • 4
  • 12