(234d) Learning to Initialize Generalized Benders Decomposition

Generalized Benders Decomposition (GBD) has been used widely to solve large scale mathematical optimization problems that arise in the operation of process systems [1-4]. In GBD the problem is decomposed into a master problem and a subproblem which interact though the complicating variables and are coordinated via the addition of cuts in the master problem. Despite the computational advantages over monolithic solution the implementation of GBD is nontrivial. The performance of Benders and Generalized Benders decomposition can be improved by problem reformulation which changes the structure of the problem and thus the decomposition, multicut implementation [5], cut generation and management [6-9] and initialization of the master problem [10]. In this work we will focus on the initialization of the master problem in the first iteration of the algorithm.

We will assume that a problem must be solved repeatedly based on updated values of the parameters p of the problem. We will consider the case where the complicating variables are continuous and the parameters of the subproblem do not change. Under these assumptions we can discretize the domain of the complicating variables into n points, compute the cuts once and add them in the master problem every time the problem must be solved with updated values of the parameters. However, the addition of all these cuts will increase the complexity of the master problem, which might increase the computational time. Therefore, given new parameters p we must decide how many cuts to add such that the solution time is minimized. The solution time y depends on the features of the problem φ, such as values of the parameters, and the number of cuts n that are added in the master problem, i.e y = f(φ,n). Given a problem with features φ, we can find the optimal number of cuts n^* by minimizing f, i.e. n^*= argmin f(φ,n). However, f is not known, i.e. this is a black box optimization problem. To overcome this problem we employ tools from machine learning to learn a surrogate model g. Specifically, we generate random values of the parameters, we solve the problem with different number of cuts in the first iteration and we record the features of the problem, the number of cuts and the CPU time. These are the training data {(φ,n)_i,y_i}_i=1^N_data. Given these data we learn the surrogate model and use it to find the optimal number of cuts, i.e. n^* = argmin g(φ,n).

We apply the proposed approach to closed loop scheduling and dynamic optimization. We follow the problem formulation proposed in [11], where N products must be manufactured and the time horizon is composed of N slots. The integrated problem considers all the transitions between the products simultaneously and the problem is solved using a hybrid multicut Generalized Benders Decomposition proposed in [12]. In this case the original problem is decomposed into a master problem which considers the scheduling decisions, the subproblems are nonlinear problems and the transitions between the products and the complicating variables are the transition times. We will consider the case where the system is an isothermal CSTR, five products must be manufactured, and disturbances affect the system. The integrated problem must be resolved for updated process information regarding product demand, price, inventory levels, time horizon, etc. We learn the surrogate model as described above using neural networks, decision trees and random forests as surrogate models. Once the surrogate models are trained, we generate 100 random disturbances and use the surrogate models to find the optimal number of cuts. The results show that this approach leads on average to 70 % reduction in total CPU time. The total CPU time is the summation of the solution time of the hybrid multicut GBD algorithm and the time required to decide the optimal number of cuts. Specifically, using random forests as surrogate model lead to 70.5% reduction, using the neural network in 71.71% reduction and the decision trees in 70.53% reduction in CPU time.

References:

[1]. Geoffrion, A.M., 1972. Generalized benders decomposition. Journal of optimization theory and applications, 10(4), pp.237-260.

[2]. Chu, Y. and You, F., 2013. Integration of production scheduling and dynamic optimization for multi-product CSTRs: Generalized Benders decomposition coupled with global mixed-integer fractional programming. Computers & Chemical Engineering, 58, pp.315-333.

[3]. Nie, Y., Biegler, L.T., Villa, C.M. and Wassick, J.M., 2015. Discrete time formulation for the integration of scheduling and dynamic optimization. Industrial & Engineering Chemistry Research, 54(16), pp.4303-4315.

[4]. 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.

[5]. You, F. and Grossmann, I.E., 2013. Multicut Benders decomposition algorithm for process supply chain planning under uncertainty. Annals of Operations Research, 210(1), pp.191-211.

[6]. Saharidis, G.K. and Ierapetritou, M.G., 2010. Improving Benders decomposition using maximum feasible subsystem (MFS) cut generation strategy. Comp Chem Eng, 34(8), pp.1237-1245.

[7]. Pacqueau, R., Soumis, F. and Hoang, L.N., 2012. A fast and accurate algorithm for stochastic integer programming, applied to stochastic shift scheduling. Groupe d'études et de recherche en analyse des décisions.

[8]. Jia, H. and Shen, S., 2021. Benders cut classification via support vector machines for solving two-stage stochastic programs. INFORMS Journal on Optimization, 3(3), pp.278-297..

[9]. Lee, M., Ma, N., Yu, G. and Dai, H., 2020. Accelerating generalized benders decomposition for wireless resource allocation. IEEE Transactions on Wireless Communications, 20(2), pp.1233-1247.

[10]. Saharidis, G.K., Boile, M. and Theofanis, S., 2011. Initialization of the Benders master problem using valid inequalities applied to fixed-charge network problems. Expert Systems with Applications, 38(6), pp.6627-6636.

[11]. Mitrai, I., and Daoutidis, P., An adaptive multi-cut decomposition based algorithm for integrated closed loop scheduling and control, Proceedings of the 14th International Symposium on Process Systems Engineering – PSE 2021+, accepted

[12]. Mitrai, I., and Daoutidis, P., A hybrid multicut Generalized Benders Decomposition for the integration of process operations and dynamic optimization, under review