Modeling Logical Constraints with Binaries (AND, OR, NOT)

Recall that a binary variable $x \in \{0,1\}$ encodes a yes/no decision. Once decisions are represented this way, we can translate logical conditions into linear constraints.

Let $x_1, x_2, \ldots, x_n \in \{0,1\}$.

• AND (both selected): $x_i = 1$ and $x_j = 1$ becomes

$$x_i + x_j = 2.$$

• OR (at least one selected): $x_i = 1$ or $x_j = 1$ becomes

$$x_i + x_j \geq 1.$$

• NOT ($x_i$ is not selected):

$$x_i = 0.$$

More generally,

• 'at least $k$ of $x_1, \ldots, x_n$ are selected': $\sum\limits_{i=1}^n x_i \geq k,$
• 'at most $k$ are selected': $\sum\limits_{i=1}^n x_i \leq k,$
• 'exactly $k$ are selected': $\sum\limits_{i=1}^n x_i = k,$
• '$x_i$ and $x_j$ cannot both be selected': $x_i + x_j \leq 1.$

For instance, a factory must run at least two of three machines $A, B, C$. With binaries $x_A, x_B, x_C,$ the rule becomes

$$x_A + x_B + x_C \geq 2.$$