Linear programming

Modeling with binary variables

Let $y, x_1, \dots, x_n \in \{0, 1\}$ be binary variables.

Logical NOT

$y = \neg x_1$

• $y = 1 - x_1$

Logical AND

$y = x_1 \land x_2$

• $y \leq x_1$
• $y \leq x_2$
• $y + 1 \geq x_1 + x_2$

Logical OR

$y = x_1 \lor x_2$

• $y \geq x_1$
• $y \geq x_2$
• $y \leq x_1 + x_2$

Logical XOR

$y = x_1 \oplus x_2$

• $y \leq x_1 + x_2$
• $y + x_1 \geq x_2$
• $y + x_2 \geq x_1$
• $y + x_1 + x_2 \leq 2$

Logical implication

$y = (x_1 \implies x_2)$

• $y \geq x_2$
• $y + x_1 \geq 1$
• $y + x_1 \leq 1 + x_2$

Linearization

Product of a real variable and a binary variable

Let $x$ be a real variable such that $0 \leq x \leq M$.
Let $y$ be a binary variable.
Let $z$ be a real variable such that $z \geq 0$.

$z = xy$

• $z \leq My$
• $z \leq x$
• $z + M (1 - y) \geq x$

Zero or greater than a constant

Let $x$ be a real variable such that $0 \leq x \leq M$.
Let $y$ be a binary variable.
Let $L$ be a real constant such that $0 \leq L \leq M$.

$x = 0$ or $x \geq L$

• $x \geq Ly$
• $x \leq My$