Generalized Disjunctive Programming

../../_images/Pyomo-GDP-150.png

The Pyomo.GDP modeling extension[1] provides support for Generalized Disjunctive Programming (GDP)[2], an extension of Disjunctive Programming[3] from the operations research community to include nonlinear relationships. The classic form for a GDP is given by:

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

Here, we have the minimization of an objective \(obj\) 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[4]. 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.

Literature References