concepts.rst

Key Concepts

Generalized Disjunctive Programming (GDP) provides a way to bridge high-level propositional logic and algebraic constraints. The GDP standard form from the index page <gdp-main-page> is repeated below.

$$\begin{aligned} \min\ obj = &\ f(x, z) \\\ \text{s.t.} \quad &\ Ax+Bz \leq d\\\ &\ g(x,z) \leq 0\\\ &\ \bigvee_{i\in D_k} \left[ \begin{gathered} Y_{ik} \\\ M_{ik} x + N_{ik} z \leq e_{ik} \\\ r_{ik}(x,z)\leq 0\\\ \end{gathered} \right] \quad k \in K\\\ &\ \Omega(Y) = True \\\ &\ x \in X \subseteq \mathbb{R}^n\\\ &\ Y \in \{True, False\}^{p}\\\ &\ z \in Z \subseteq \mathbb{Z}^m \end{aligned}$$

Original support in Pyomo.GDP focused on the disjuncts and disjunctions, allowing the modelers to group relational expressions in disjuncts, with disjunctions describing logical-OR relationships between the groupings. As a result, we implemented the Disjunct and Disjunction objects before BooleanVar and the rest of the logical expression system. Accordingly, we also describe the disjuncts and disjunctions first below.

Disjuncts

Disjuncts represent groupings of relational expressions (e.g. algebraic constraints) summarized by a Boolean indicator variable Y through implication:

$$\begin{aligned} \left. \begin{aligned} & Y_{ik} \Rightarrow & M_{ik} x + N_{ik} z &\leq e_{ik}\\\ & Y_{ik} \Rightarrow & r_{ik}(x,z) &\leq 0 \end{aligned} \right.\qquad \forall i \in D_k, \forall k \in K \end{aligned}$$

Logically, this means that if Y_ik = True, then the constraints M_ikx + N_ikz ≤ e_ik and r_ik(x, z) ≤ 0 must be satisfied. However, if Y_ik = False, then the corresponding constraints are ignored. Note that Y_ik = False does not imply that the corresponding constraints are violated.

Disjunctions

Disjunctions describe a logical OR relationship between two or more Disjuncts. The simplest and most common case is a 2-term disjunction:

$$\begin{aligned} \left[\begin{gathered} Y_1 \\\ \exp(x_2) - 1 = x_1 \\\ x_3 = x_4 = 0 \end{gathered} \right] \bigvee \left[\begin{gathered} Y_2 \\\ \exp\left(\frac{x_4}{1.2}\right) - 1 = x_3 \\\ x_1 = x_2 = 0 \end{gathered} \right] \end{aligned}$$

The disjunction above describes the selection between two units in a process network. Y₁ and Y₂ are the Boolean variables corresponding to the selection of process units 1 and 2, respectively. The continuous variables x₁, x₂, x₃, x₄ describe flow in and out of the first and second units, respectively. If a unit is selected, the nonlinear equality in the corresponding disjunct enforces the input/output relationship in the selected unit. The final equality in each disjunct forces flows for the absent unit to zero.

Boolean Variables

Boolean variables are decision variables that may take a value of True or False. These are most often encountered as the indicator variables of disjuncts. However, they can also be independently defined to represent other problem decisions.

Note

Boolean variables are not intended to participate in algebraic expressions. That is, 3 × True does not make sense; hence, x = 3Y₁ does not make sense. Instead, you may have the disjunction

$$\begin{aligned} \left[\begin{gathered} Y_1 \\\ x = 3 \end{gathered} \right] \bigvee \left[\begin{gathered} \neg Y_1 \\\ x = 0 \end{gathered} \right] \end{aligned}$$

Logical Propositions

Logical propositions are constraints describing relationships between the Boolean variables in the model.

These logical propositions can include:

Operator	Example	Y1	Y2	Result
Negation	¬Y1	True False		False True
Equivalence	Y1 ⇔ Y2	True True False False	True False True False	True False False True
Conjunction	Y1 ∧ Y2	True True False False	True False True False	True False False False
Disjunction	Y1 ∨ Y2	True True False False	True False True False	True True True False
Exclusive OR	Y1 ⊻ Y2	True True False False	True False True False	False True True False
Implication	Y1 ⇒ Y2	True True False False	True False True False	True False True True