Generalized Disjunctive Programming

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.

Pyomo.GDP Contents

• Key Concepts
  • Disjuncts
  • Disjunctions
  • Boolean Variables
  • Logical Propositions
• Modeling in Pyomo.GDP
  • Disjunctions
  • Logical Propositions
  • Advanced LogicalConstraint Examples
  • Additional Examples
• Solving Logic-based Models with Pyomo.GDP
  • Flexible Solution Suite
  • Reformulations
  • Direct GDP solvers
  • References

Literature References

[1]

Chen, Q., Johnson, E. S., Bernal, D. E., Valentin, R., Kale, S., Bates, J., Siirola, J. D. and Grossmann, I. E. (2021). Pyomo.GDP: an ecosystem for logic based modeling and optimization development, Optimization and Engineering (pp. 1-36).https://doi.org/10.1007/s11081-021-09601-7

[2]

Raman, R., & Grossmann, I. E. (1994). Modelling and computational techniques for logic based integer programming. Computers & Chemical Engineering, 18(7), 563–578. https://doi.org/10.1016/0098-1354(93)E0010-7

[3]

Balas, E. (1985). Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems. SIAM Journal on Algebraic Discrete Methods, 6(3), 466–486. https://doi.org/10.1137/0606047

[4]

Grossmann, I. E., & Trespalacios, F. (2013). Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming. AIChE Journal, 59(9), 3276–3295. https://doi.org/10.1002/aic.14088