Skip to main content
Became Hot Network Question
Improved TeX formatting
Source Link
TheSimpliFire
  • 5.5k
  • 5
  • 23
  • 56

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}\begin{equation} \bigvee A \implies \bigvee B \\ \overline{\bigvee A} \bigvee \left(\bigvee B\right) \\ \left(\bigwedge_{a \in A} \overline a\right) \bigvee \left(\bigvee B\right) \\ \left(\bigwedge_{a \in A} (1-a)\right) \bigvee \left(\bigvee B\right) \\ \left(\prod_{a \in A} (1-a)\right) \bigvee \left(\sum_{b \in B} b\right) \\ \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$A$. Can this be expressed in terms of linear constraints?

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?

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 \left(\bigvee B\right) \\ \left(\bigwedge_{a \in A} \overline a\right) \bigvee \left(\bigvee B\right) \\ \left(\bigwedge_{a \in A} (1-a)\right) \bigvee \left(\bigvee B\right) \\ \left(\prod_{a \in A} (1-a)\right) \bigvee \left(\sum_{b \in B} b\right) \\ \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?

edited title
Link
LarrySnyder610
  • 13.2k
  • 3
  • 42
  • 106

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

Source Link
ephemeral
  • 917
  • 4
  • 12

Expressing an implication as ILP where each implication term comprises a chain or 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?