2021 Annual Meeting

(106e) Discrete-Steepest Descent: A Solution Method for Process Synthesis Generalized Disjunctive Programs

Authors

Bernal, D. - Presenter, Universities Space Research Association
Ovalle, D., Universidad de los Andes
Liñán, D., University of Waterloo
Ricardez-Sandoval, L., University of Waterloo
Gomez, J., Universidad de los Andes - Columbia
Grossmann, I., Carnegie Mellon University
The optimal process design and operation challenge chemical engineers, specifically in the Process Systems Engineering(PSE) community. Chemical processes need to satisfy operational, economic, and environmental goals, which can be integrated through optimal design, i.e., an area studied within Process Synthesis [1,2,3]. A promising method that tackles the design of processes with structural decisions is the superstructure approach, where different possible process flowsheets are combined into a single structure. Hence, the objective is to select which units and interconnections lead to the optimal process, considering both operating conditions and desired specifications [4]. This superstructure method leads to a mathematical optimization problem that can be tackled using tools borrowed from Mathematical Programming. Moreover, due to the usual presence of both nonlinear terms and discrete variables, these problems can be posed as Mixed-Integer Nonlinear Programs (MINLP). The solution to these optimization problems is challenging given their combinatorial and nonconvex nature. Therefore the Generalized Disjunctive Programming (GDP) framework has been proposed to resolve the challenges of MINLP solution strategies [5]. Accordingly, the main contribution of this work is to consolidate the Discrete-Steepest Descent Algorithm (D-SDA) as an efficient GDP solution method through its implementation and automatization in Pyomo. The D-SDA exploits a mathematical structure often present in GDP superstructures, i.e., the inherent positional order present in superstructure design problems.

A common objective in process design is to designate discrete locations to units or streams over a superstructure, e.g., unit operations can be included in series, such as trays in distillation columns or positions in reactor networks. When posing these problems as GDP, Boolean variables represent the discrete decisions relevant to a given superstructure choice together with all the constraints associated with it. These Boolean variables belong to an ordered set representing positions of possible locations within the superstructure. Furthermore, Boolean variables are usually subject to knapsack equality constraints, where only a fixed number of the Boolean variables within that ordered set need to be set to True, e.g., three trays need to contain catalyst in a reactive distillation column [6]. Knowledge of this mathematical structure is integrated into the proposed algorithm to efficiently explore the discrete solution space through a variable reformulation technique.

We propose the Discrete-Steepest Descent Algorithm (D-SDA) as a systematic algorithm tailor-designed to solve GDP superstructure problems with cardinality or knapsack equality constraints defined over ordered Boolean variables. The D-SDA relies on a reformulation of the Boolean variables in the GDP problem into integer choices named external variables[7]. The external variables provide a succinct representation of locations within the superstructure by exploiting its characteristic of sequentially ordered positions. This variable selection reduces the problem’s dimensionality, as it integrates several Boolean variables into just one external variable and allows the method to efficiently explore the combinatorial space of the discrete variables, referred to as the neighborhood. The algorithm uses search criteria such as neighborhood, and line searches to perform a systematic scouting of the discrete feasible region. This exploration leads to an efficient choice of external variables resulting in Nonlinear Programming (NLP) subproblems that are solved sequentially until a local optimum is found. The D-SDA uses as termination criterion the integrally local optimality [8],allowing it to find local optima that are not necessarily considered by other MINLP and GDP solution algorithms. Motivated by this technique’s early success for complex and highly nonconvex MINLPs [7,6,9], we present a formal description of the algorithm within the scope of GDP, together with an open-source implementation of the method.

The D-SDA is presented as a tailored solution method for GDP. The specialized solution methods for GDP are usually based on generalizing algorithms for MINLP, where the optimization problems are decomposed, so the discrete variables are fixed and allow to solve the problem only in terms of the continuous variables. Furthermore, we show that the D-SDA is related to other existing GDP solvers such as Logic-based Branch-and-Bound (LBB) and the Logic-based Outer-Approximation (LOA) [10]; that is, the D-SDA reduces to these algorithms in limiting cases. The D-SDA does not provide a dual bound for the optimal solution because it does not entail the optimal solution of a relaxation of the original problem. Thus, the D-SDA’s optimality criterion does not rely on computing the optimality gap as LOA and LBB. Instead, building upon the developments of [8], the D-SDA’s stopping criteria are modified to guarantee local integral optimal convergence.

We implemented the D-SDA method in an extensible Python implementation compatible with Pyomo.GDP [10] to address discrete optimization problems in Process Synthesis [11]. The performance of this algorithm is compared against MINLP and GDP solvers by addressing three process superstructure problems: A GDP reformulation of the volume minimization of a series of Continuously Stirred Tank Reactors (CSTR) considered by Liñán et al.[7], the optimal economic design of a tray-distillation column proposed by Ghouse et al.[12], and a GDP reformulation of the optimal design for chemical batch processing presented by Kocis and Grossmann[13]. For the CSTR superstructure, the proposed D-SDA framework resulted in a more efficient strategy to obtain the globally optimal solution in computational time than state-of-the-art MINLP solvers. Furthermore, even with the problem’s GDP reformulation, the D-SDA performed faster than other tailored GDP solvers such as LOA and LBB. The D-SDA proved to be more efficient in the distillation column example than both MINLP and GDP solvers and improved the best-known GDP solution to this challenging optimization problem. For the batch processing problem, MINLP solvers performed slightly faster than the proposed D-SDA method; nevertheless, it converged to the optimum within a few seconds, a time within the same order of magnitude as state-of-the-art nonlinear discrete optimization solvers.

The examples mentioned herein, together with a general D-SDA implementation, were written in Python and made compatible with the open-source algebraic modeling language Pyomo.GDP [10], and can be found in an openly-available GitHub repository (https://github.com/bernalde/dsda-gdp).

References

[1] E. Pistikopoulos, A. Barbosa-Povoa, J. H. Lee, R. Misener, A. Mitsos, G. Reklaitis, V. Venkatasubramanian, F. You, and R. Gani, “Process systems engineering–the generation next?” Computers & Chemical Engineering, p.107252, 2021.

[2]Q. Chen and I. Grossmann, “Recent developments and challenges in optimization-based process synthesis,” Annual review of chemical and biomolecular engineering, vol. 8, pp. 249–283, 2017.

[3]M. Rafiei and L. A. Ricardez-Sandoval, “New frontiers, challenges, and opportunities in integration of design and control for enterprise-wide sustainability,” Computers & Chemical Engineering, vol. 132, p. 106610, Jan. 2020.

[4]H. Yeomans and I. E. Grossmann, “A systematic modeling framework of superstructure optimization in process synthesis,” Computers & Chemical Engineering, vol. 23, no. 6, pp. 709–731, 1999.

[5]I. E. Grossmann and F. Trespalacios, “Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming, ”AIChE Journal, vol. 59, no. 9, pp. 3276–3295, 2013.

[6]D. A. Liñán, D. E. Bernal, L. A. Ricardez-Sandoval, and J. M. Gómez, “Optimal design of superstructures for placing units and streams with multiple and ordered available locations. Part II: Rigorous design of catalytic distillation columns, ”Computers & Chemical Engineering, vol. 139, p. 106845, 2020.

[7]——, “Optimal design of superstructures for placing units and streams with multiple and ordered available locations. Part I: A new mathematical framework, ”Computers & Chemical Engineering, vol. 137, p. 106794,2020.

[8] K. Murota, “Discrete convex analysis, ”Mathematical Programming, vol. 83, no. 1, pp. 313–371, 1998.

[9]D. A. Liñán, D. E. Bernal, J. M. Gomez, and L. A. Ricardez-Sandoval, “Optimal synthesis and design of catalytic distillation columns: A rate-based modeling approach, ”Chemical Engineering Science, vol. 231, p. 116294, 2021.

[10]Q. Chen, E. S. Johnson, D. E. Bernal, R. Valentin, S. Kale, J. Bates, J. D. Siirola, and I. E. Grossmann, “Pyomo.gdp: an ecosystem for logic based modeling and optimization development.”

[11]L. Biegler, I. Grossmann, and A. Westerberg, Systematic Methods of Chemical Process Design, ser. Physical and Chemical Engineering Sciences. Prentice Hall PTR, 1997.

[12]J. H. Ghouse, Q. Chen, M. A. Zamarripa, A. Lee, A. P. Burgard, I. E. Grossmann, and D. C. Miller, “A comparative study between GDP and NLP formulations for conceptual design of distillation columns,” in Computer Aided Chemical Engineering. Elsevier, 2018, vol. 44, pp. 865–870.

[13]G. R. Kocis and I. E. Grossmann, “Global optimization of nonconvex mixed-integer nonlinear programming(MINLP) problems in process synthesis, ”Industrial & engineering chemistry research, vol. 27, no. 8, pp. 1407–1421,1988.