(234h) A Benders Decomposition Framework for the Optimization of Generalized Disjunctive Programming Problems with Ordered Boolean Variables

A current challenge in chemical process optimization is the development of reliable algorithms that can solve complex problems of industrial significance [1]. Also, the need for specialized and improved optimization techniques is increasing with the development of rigorous multi-scale models and frameworks that integrate multiple decision layers such as simultaneous design and control [2]. In this work, disjunctive nonlinear optimization problems with both continuous and logical decisions that affect the structure of the problem are considered. For instance, consider the selection between two process alternatives, e.g., reaction followed by separation vs reactive distillation. In this case, the optimization model must account for the constraints of both process alternatives through a disjunction, and it must also consider that their constraints are mutually exclusive. A modeling alternative that can deal with constraints and variables of this type is Generalized Disjunctive Programming (GDP). The key idea in GDP is to provide a logical modeling framework, where switching decisions between groups of constraints are represented through Boolean variables that activate/deactivate constraints within disjunctions [3]. GDP formulations are very general, e.g., there is an equivalent Mixed-Integer Nonlinear Programming (MINLP) representation for any GDP model [4]. Additionally, the GDP representation has multiple advantages over the classic MINLP formulation including (1) the user can explicitly indicate the relationship between Boolean variables and the constraints they activate/deactivate; (2) the model is not restricted to particular relaxations, e.g., Big-M; (3) numerical issues related to the interaction of continuous and discrete variables are avoided, e.g., zero flow issues [3,5].

GDP problems are commonly reformulated as MINLP problems and then solved using traditional MINLP techniques. However, this procedure precludes the exploitation of the GDP advantages discussed above. Thus, logic-based optimization algorithms such as Logic-based Outer Approximation (L-OA) and Logic-based Branch and Bound (L-BB) have been suggested to take advantage of GDP formulations [6,7]. The key difference between these algorithms and the traditional Outer Approximation and Branch and Bound techniques is that logic-based algorithms solve nonlinear subproblems in a reduced space, i.e., nonlinear constraints and variables related to inactive disjunctions are omitted from the subproblem model. Hence, smaller subproblems are solved at each iteration, and numerical issues related to inactive disjunctions are avoided [8]. In this work, a special case where Boolean variables in the GDP formulation follow an ordered structure is considered. This situation is common in chemical engineering applications, e.g., number of units in series/parallel in a reactor superstructure; selection of the most sensitive stage for distillation temperature control applications; number of times a task is executed during a production schedule. Henceforth, these discrete variables that define ordered discrete decisions will be referred to as external variables. Although L-OA or L-BB algorithms can be applied to solve the problems explained above, these strategies do not account for the ordered nature of discrete decisions in their solution routines. Thus, they may converge to suboptimal solutions because local solutions that can be potentially inferred from ordered Boolean decisions are ignored by these strategies. Recently, it was found that when ordered Boolean variables are explicitly accounted for as external variables, it is possible to apply a logic-based Discrete-Steepest Descent Algorithm (LD-SDA) that captures the ordered nature of the decisions. A recent study has shown that the LD-SDA performs better than logic-based and traditional MINLP algorithms when Boolean variables have an ordered structure [9]. Nevertheless, the LD-SDA requires a user-provided feasible initialization, which prohibits its application as a general-purpose solver. Moreover, it is limited to local optimization only. To alleviate these limitations, it is essential to investigate alternative logic-based strategies to solve GDP problems with Boolean variables that follow an ordered structure.

The aim of this work is to introduce the Logic-based Discrete-Benders Decomposition (LD-BD) for GDP optimization problems with ordered Boolean variables. This algorithm was developed under the Logic-Based Benders Decomposition framework [10], which allowed to generalize the Benders Decomposition algorithm to nonlinear GDP problems with ordered Boolean variables. The LD-BD iteratively solves a master problem and a subproblem until convergence. The master problem fixes the value of Boolean variables, and the subproblem solves the Nonlinear Programming (NLP) problem with fixed Boolean variables in a reduced space, i.e., constraints in inactive disjunctions are ignored. Then, the subproblem computes Benders cuts (i.e., constraints) which are passed to the master problem to obtain a new fixed value of Boolean variables in a new iteration. The algorithm stops when the objective functions from the master problem and the subproblem are within a tolerance criterion. This work presents a novel strategy to obtain Benders cuts based on the solution of the subproblem and the NLPs obtained after fixing the Boolean variables within a neighborhood of the current subproblem. This neighborhood can be defined thanks to the ordered representation of Boolean variables through external variables. In addition, Benders cuts calculated at each iteration are constantly refined such that suboptimal solutions are avoided [11]. Also, a pre-processing step is implemented to obtain a starting feasible solution through the minimization of an infeasibility measure, which allows to guarantee convergence when initializing the problem from an infeasible point. To increase the likelihood of convergence to the global optimum, the LD-BD can be warm-started using random sampling strategies. Overall, these characteristics make the LD-BD an improved solution strategy relative to the LD-SDA for GDP problems with ordered Boolean variables.

The LD-BD strategy was applied to the optimal synthesis of two case studies available in the literature. The first case study is a conventional distillation column that separates an equimolar mixture of benzene and toluene; the objective of this case study is to optimize the process economics [5]. In this case, Boolean variables represent the feed location and the number of stages. To test the performance of the LD-BD to handle discrete decisions, the problem was initialized from multiple feasible and infeasible configurations of the Boolean variables. The results show that, in contrast to the L-OA, L-BB, and LD-SDA methods, the LD-BD was able to converge to the global optimum from every initialization in shorter computational times than those reported by L-OA and L-BB. Thus, although the LD-BD is a local optimization strategy, it converges to better solutions than those obtained by the currently available local logic-based solvers. The warm-start capabilities of the LD-BD were tested with a second case study that considers the optimization of multiple CSTRs in series with a recycle [9]. In this case, Boolean variables represent the number of reactors in series and the location of the recycle. The results show that finding the global optimum highly depends on the number of random points sampled. Based on the above, the proposed LD-BD method is a reliable strategy to solve optimal synthesis problems with ordered discrete decisions that emerge in chemical engineering applications.

References

[1] E.N. Pistikopoulos, A. Barbosa-Povoa, J.H. Lee, R. Misener, A. Mitsos, G.V. Reklaitis, V. Venkatasubramanian, F. You, R. Gani, Process systems engineering – The generation next?, Computers & Chemical Engineering. 147 (2021) 107252. https://doi.org/10.1016/j.compchemeng.2021.107252.

[2] B. Burnak, N.A. Diangelakis, E.N. Pistikopoulos, Towards the Grand Unification of Process Design, Scheduling, and Control—Utopia or Reality?, Processes. 7 (2019) 461. https://doi.org/10.3390/pr7070461.

[3] M.L. Bynum, G.A. Hackebeil, W.E. Hart, C.D. Laird, B.L. Nicholson, J.D. Siirola, J.-P. Watson, D.L. Woodruff, Generalized Disjunctive Programming, in: M.L. Bynum, G.A. Hackebeil, W.E. Hart, C.D. Laird, B.L. Nicholson, J.D. Siirola, J.-P. Watson, D.L. Woodruff (Eds.), Pyomo — Optimization Modeling in Python, Springer International Publishing, Cham, 2021: pp. 171–180. https://doi.org/10.1007/978-3-030-68928-5_11.

[4] I.E. Grossmann, Review of Nonlinear Mixed-Integer and Disjunctive Programming Techniques, Optimization and Engineering. 3 (2002) 227–252. https://doi.org/10.1023/A:1021039126272.

[5] J.H. Ghouse, Q. Chen, M.A. Zamarripa, A. Lee, A.P. Burgard, I.E. Grossmann, D.C. Miller, A comparative study between GDP and NLP formulations for conceptual design of distillation columns, in: M.R. Eden, M.G. Ierapetritou, G.P. Towler (Eds.), Computer Aided Chemical Engineering, Elsevier, 2018: pp. 865–870. https://doi.org/10.1016/B978-0-444-64241-7.50139-7.

[6] M. Türkay, I.E. Grossmann, Logic-based MINLP algorithms for the optimal synthesis of process networks, Computers & Chemical Engineering. 20 (1996) 959–978. https://doi.org/10.1016/0098-1354(95)00219-7.

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

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

[9] D.E. Bernal, D. Ovalle, D.A. Liñán, L.A. Ricardez-Sandoval, J.M. Gómez, I.E. Grossmann, Process Superstructure Optimization through Discrete Steepest Descent Optimization: a GDP Analysis and Applications in Process Intensification [Accepted for publication], in: Computer Aided Chemical Engineering, Elsevier, 2022.

[10] J.N. Hooker, G. Ottosson, Logic-based Benders decomposition, Math. Program., Ser. A. 96 (2003) 33–60. https://doi.org/10.1007/s10107-003-0375-9.

[11] G.R. Raidl, T. Baumhauer, B. Hu, Boosting an Exact Logic-Based Benders Decomposition Approach by Variable Neighborhood Search, Electronic Notes in Discrete Mathematics. 47 (2015) 149–156. https://doi.org/10.1016/j.endm.2014.11.020.