(104b) Extending Generalized Disjunctive Programming to Model Hierarchical Systems

Modeling systems with discrete-continuous decisions is commonly done in algebraic form with mixed-integer programming models, which can be linear or nonlinear in the continuous variables. A more systematic approach to modeling such systems is to use Generalized Disjunctive Programming (GDP) (Chen & Grossmann, 2019; Grossmann & Trespalacios, 2013), which generalizes the Disjunctive Programming paradigm proposed by Balas (2018). GDP allows modeling systems from a logic-based level of abstraction that captures the fundamental rules governing such systems via algebraic constraints and logic. The models obtained via GDP can then be reformulated into the pure algebraic form best suited for the application of interest. The two main reformulation strategies are the Big-M reformulation (Nemhauser & Wolsey, 1999; Trespalacios & Grossmann, 2015) and the Convex-Hull reformulation (Lee & Grossmann, 2000), the latter of which yields tighter models than those typically used in standard mixed-integer programming (Grossmann & Lee, 2003).

Although GDP provides a more general way of modeling systems, it warrants further generalization for systems presenting a hierarchical structure. Examples of hierarchical models are those that involve design and planning decisions (van den Heever & Grossmann, 1999), and those that involve long-term planning decisions coupled to short-term scheduling decisions (Maravelias & Sung, 2009). Such systems can be modelled via nested disjunctions inside the GDP formulation (van den Heever & Grossmann, 1999). More specifically, nested disjunctions correspond to disjunctions that in addition to involving algebraic or propositional logic constraints, may also contain as constraints one or several additional disjunctions. We denote these more general GDP problems Nested GDP (NGDP). Methods for transforming these NGDPs models into algebraic discrete-continuous models have not been formalized yet. Previous works have suggested either reformulating such models via a flattening approach, followed by an algebraic reformulation (Vecchietti & Grossmann, 2000), or else via an iterative inside-out reformulation (van den Heever & Grossmann, 1999). In this work, we study these two reformulation approaches. We formalize the flattening approach to convert NGDPs to GDPs, and then reformulate to algebraic discrete-continuous models via Big-M or Convex-Hull reformulations to MI(N)LPs. We also formalize the inside-out or direct approach to reformulate NGDPs to MI(N)LPs. The tightness of the flattening and inside-out approaches are compared, as well as the size in terms of the 0-1 and continuous variables, and the nature of the constraints. Computational results are presented with examples from the areas of process synthesis of flowsheets and optimization of electric power expansion planning with reliability considerations. The results show the computational benefits of the direct (inside-out) reformulation of the NGDP.

Keywords: Generalized Disjunctive Programming, Nested Disjunctions, Discrete-Continuous Optimization

References:

Balas, E. (2018). Disjunctive Programming. In Disjunctive Programming. Springer International Publishing. https://doi.org/10.1007/978-3-030-00148-3

Chen, Q., & Grossmann, I. E. (2019). Modern Modeling Paradigms Using Generalized Disjunctive Programming. Processes, 7(11). https://doi.org/10.3390/pr7110839

Grossmann, I. E., & Lee, S. (2003). Generalized convex disjunctive programming: Nonlinear convex hull relaxation. Computational Optimization and Applications, 26(1), 83–100. https://doi.org/10.1023/A:1025154322278

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

Lee, S., & Grossmann, I. E. (2000). New algorithms for nonlinear generalized disjunctive programming. Computers & Chemical Engineering, 24(9–10), 2125–2141. https://doi.org/10.1016/S0098-1354(00)00581-0

Maravelias, C. T., & Sung, C. (2009). Integration of production planning and scheduling: Overview, challenges and opportunities. Computers & Chemical Engineering, 33(12), 1919–1930. https://doi.org/10.1016/J.COMPCHEMENG.2009.06.007

Nemhauser, G. L., & Wolsey, L. A. (1999). Integer and combinatorial optimization. Wiley.

Trespalacios, F., & Grossmann, I. E. (2015). Improved Big-M reformulation for generalized disjunctive programs. Computers & Chemical Engineering, 76, 98–103. https://doi.org/10.1016/J.COMPCHEMENG.2015.02.013

van den Heever, S. A., & Grossmann, I. E. (1999). Disjunctive multiperiod optimization methods for design and planning of chemical process systems. Computers & Chemical Engineering, 23(8), 1075–1095. https://doi.org/10.1016/S0098-1354(99)00273-2

Vecchietti, A., & Grossmann, I. E. (2000). Modeling issues and implementation of language for disjunctive programming. Computers & Chemical Engineering, 24(9–10), 2143–2155. https://doi.org/10.1016/S0098-1354(00)00582-2