(104d) A Hybrid Multicut Generalized Benders Decomposition Algorithm for the Integration of Process Operations and Dynamic Optimization

The integration of process operations, i.e. planning and scheduling, and dynamic optimization is considered as a promising avenue to improve the economic performance of process systems by exploiting the interactions between the different decision levels [1]. However, the solution of integrated planning, scheduling, and dynamic optimization problems is computationally challenging due to the nonlinear behavior of most process systems, the discrete nature of planning/scheduling decisions and the different time scales that are involved [2,3]. Decomposition based solution algorithms can be used to improve the tractability of such problems by exploiting the underlying structure of the problem [4,5]. However, their implementation is nontrivial since a decomposition of the problem itself is necessary and the structure of the problem depends on the formulation of the problem.

In this work we propose a new formulation of the integrated planning, scheduling, and dynamic optimization problem for continuous single stage processes. We assume that several products (N_pr) must be manufactured, the time horizon is decomposed into N_p planning periods and each planning period is composed of N_s slots. Motivated by the formulation of the integrated scheduling and dynamic optimization problem for batch systems [6], we consider all the transitions between the products for all slots and periods simultaneously. The resulting integrated problem is a large scale Mixed Integer Nonlinear Problem (MINLP) whose monolithic solution is intractable. Analysis of the structure of the problem via Stochastic Blockmodeling [7,8] reveals that in the proposed formulation the planning/scheduling variables and constraints are coupled with the dynamic optimization variables and constraints for each transition only via the transition times. Based on the identified structure we propose a multicut Generalized Benders Decomposition algorithm, where the Benders cuts approximate the cost associated with the transitions for each slot and period. The master problem is a MINLP solved with Gurobi [9] and the subproblems are nonlinear problems solved with IPOPT [10]. In order to reduce further the computational time we propose a hybrid multicut Generalized Benders Decomposition algorithm where the cut associated with one transition in one slot and period is added for all slots and periods.

We apply the two algorithms in two case studies. In the first we assume that the system is an isothermal CSTR and we compare the proposed formulation and decomposition based algorithms with the application of Generalized Benders Decomposition based on the problem formulation proposed in [2] and the decomposition proposed in [5]. We assume that four products must be produced in two planning periods. The proposed multicut algorithm leads to 90% reduction in CPU and the hybrid algorithm to 96% reduction, compared to the approach proposed in [2,5]. Both algorithms improve the both the upper and lower bounds faster compared to the application of GBD based on [2,5]. Also, the addition of multiple cuts per transition in the hybrid algorithm lead to further reduction in CPU time (compared to the mutlicut algorithm), since more information is added in the master problem in each iteration.

In the second case study we analyze the effect of the planning periods on the performance of the proposed algorithms. We assume that the system is a polymerization reactor where 4 products must be manufactured. We vary the number of planning periods from 4 to 10 and compare the computational performance of the proposed algorithms and the approach proposed in [2,5]. We show that the proposed algorithms solve the problem in reduced computational time and the solution that is obtained is better, i.e. the value of the objective function is higher, for all planning periods. Specifically, the multicut algorithm reduces the CPU time up to 94% and the hybrid algorithm up to 98%, whereas the value of the objective function is improved up to 6.4%.

References:

[1]. Daoutidis, P., Lee, J. H., Harjunkoski, I., Skogestad, S., Baldea, M., & Georgakis, C. (2018). Integrating operations and control: A perspective and roadmap for future research. Computers & Chemical Engineering, 115, 179-184.

[2]. Gutiérrez-Limón, Miguel Angel, Antonio Flores-Tlacuahuac, and Ignacio E. Grossmann. "MINLP formulation for simultaneous planning, scheduling, and control of short-period single-unit processing systems." Industrial & Engineering Chemistry Research 53, no. 38 (2014): 14679-14694.

[3]. Charitopoulos, V.M., Dua, V. and Papageorgiou, L.G., 2017. Traveling salesman problem-based integration of planning, scheduling, and optimal control for continuous processes. Industrial & Engineering Chemistry Research, 56(39), pp.11186-11205.

[4]. Mora-Mariano, D., Gutiérrez-Limón, M.A. and Flores-Tlacuahuac, A., 2020. A Lagrangean decomposition optimization approach for long-term planning, scheduling and control. Computers & Chemical Engineering, 135, p.106713.

[5]. Mitrai, I. and Daoutidis, P., 2021. Efficient Solution of Enterprise-Wide Optimization Problems Using Nested Stochastic Blockmodeling. Industrial & Engineering Chemistry Research, 60(40), pp.14476-14494.

[6]. Chu, Y. and You, F., 2013. Integrated scheduling and dynamic optimization of complex batch processes with general network structure using a generalized benders decomposition approach. Industrial & Engineering Chemistry Research, 52(23), pp.7867-7885.

[7]. Mitrai, I., Tang, W. and Daoutidis, P., 2021. Stochastic blockmodeling for learning the structure of optimization problems. AIChE Journal, p.e17415.

[8]. Peixoto, T.P., 2019. Bayesian stochastic blockmodeling. Advances in network clustering and blockmodeling, pp.289-332.

[9]. Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, accessed: 2021-08-31 (2021).URL https://www.gurobi.com

[10]. Wächter, A. and Biegler, L.T., 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming, 106(1), pp.25-57.