Generalized Disjunctive Programming
The Pyomo.GDP modeling extension [PyomoGDP-proceedings]
[PyomoGDP-paper] provides support for Generalized Disjunctive
Programming (GDP) [RG94], an extension of Disjunctive Programming
[Bal85] from the operations research community to include nonlinear
relationships. The classic form for a GDP is given by:
\[\begin{array}{ll}
\min & f(x, z) \\
\mathrm{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{array}\]
Here, we have the minimization of an objective \(f(x, z)\) subject to global linear constraints \(Ax+Bz \leq d\) and nonlinear constraints \(g(x,z) \leq 0\), with conditional linear constraints \(M_{ik} x + N_{ik} z \leq e_{ik}\) and nonlinear constraints \(r_{ik}(x,z)\leq 0\).
These conditional constraints are collected into disjuncts \(D_k\), organized into disjunctions \(K\). Finally, there are logical propositions \(\Omega(Y) = True\).
Decision/state variables can be continuous \(x\), Boolean \(Y\), and/or integer \(z\).
GDP is useful to model discrete decisions that have implications on the
system behavior [GT13]. For example, in process design, a
disjunction may model the choice between processes A and B. If A is
selected, then its associated equations and inequalities will apply;
otherwise, if B is selected, then its respective constraints should be
enforced.
Modelers often ask to model if-then-else relationships.
These can be expressed as a disjunction as follows:
\begin{gather*}
\left[\begin{gathered}
Y_1 \\
\text{constraints} \\
\text{for }\textit{then}
\end{gathered}\right]
\vee
\left[\begin{gathered}
Y_2 \\
\text{constraints} \\
\text{for }\textit{else}
\end{gathered}\right] \\
Y_1 \veebar Y_2
\end{gather*}
Here, if the Boolean \(Y_1\) is True, then the constraints in the first disjunct are enforced; otherwise, the constraints in the second disjunct are enforced.
The following sections describe the key concepts, modeling, and solution approaches available for Generalized Disjunctive Programming.