Skip to content

Latest commit

 

History

History
79 lines (62 loc) · 3.68 KB

index.rst

File metadata and controls

79 lines (62 loc) · 3.68 KB
Raw

Generalized Disjunctive Programming

image

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

$$\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}$$

Here, we have the minimization of an objective obj subject to global linear constraints Ax + Bz ≤ d and nonlinear constraints g(x, z) ≤ 0, with conditional linear constraints Mikx + Nikz ≤ eik and nonlinear constraints rik(x, z) ≤ 0. These conditional constraints are collected into disjuncts Dk, organized into disjunctions K. Finally, there are logical propositions Ω(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 behavior4. 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{aligned} \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*} \end{aligned}$$

Here, if the Boolean Y1 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.

concepts modeling solving

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↩