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 is repeated below.

\[\begin{split}\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{split}\]

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{split}\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{split}\]

Logically, this means that if \(Y_{ik} = True\), then the constraints \(M_{ik} x + N_{ik} z \leq e_{ik}\) and \(r_{ik}(x,z) \leq 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{split}\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{split}\]

The disjunction above describes the selection between two units in a process network. \(Y_1\) and \(Y_2\) are the Boolean variables corresponding to the selection of process units 1 and 2, respectively. The continuous variables \(x_1, x_2, x_3, x_4\) 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 \times \text{True}\) does not make sense; hence, \(x = 3 Y_1\) does not make sense. Instead, you may have the disjunction

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

Logical Propositions

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

These logical propositions can include:

Operator	Example	\(Y_1\)	\(Y_2\)	Result
Negation	\(\neg Y_1\)	`True` `False`		`False` `True`
Equivalence	\(Y_1 \Leftrightarrow Y_2\)	`True` `True` `False` `False`	`True` `False` `True` `False`	`True` `False` `False` `True`
Conjunction	\(Y_1 \land Y_2\)	`True` `True` `False` `False`	`True` `False` `True` `False`	`True` `False` `False` `False`
Disjunction	\(Y_1 \lor Y_2\)	`True` `True` `False` `False`	`True` `False` `True` `False`	`True` `True` `True` `False`
Exclusive OR	\(Y_1 \veebar Y_2\)	`True` `True` `False` `False`	`True` `False` `True` `False`	`False` `True` `True` `False`
Implication	\(Y_1 \Rightarrow Y_2\)	`True` `True` `False` `False`	`True` `False` `True` `False`	`True` `False` `True` `True`