(491d) Efficient Solution of Mixed Integer Model Predictive Control Problems Via Benders Decomposition

Mixed integer model predictive control (MPC) is a natural strategy for controlling systems where discrete and continuous decisions are taken simultaneously. The discrete nature of these problems can arise either due to discrete system dynamics (e.g., piece-wise affine) or the presence of discrete variables related to the operation of the system [1-3]. In these cases, the resulting optimization problem is a Mixed Integer Programming (MIP) problem that must be solved repeatedly online.

The online solution of such MIP problems is a daunting task that limits the implementation of mixed integer MPC. The standard solution approach for MIP problems is the branch and bound one [4,5], which although can solve the problem to global optimality, is slow for online applications. Another approach is to compute the solution of the MIP problem for every value of the problem's parameters offline using multiparametric programming [6,7]. However, this is computationally expensive for discrete nonlinear systems with many states. Finally, one can exploit the underlying structure of the problem and use decomposition-based solution methods such as Generalized Benders Decomposition (GBD) [10,11].

GBD is based on the observation that if a subset of the variables, called complicating variables, is fixed, the problem can be solved faster. In GBD, the original problem is decomposed into a master problem, which considers the binary variables, and a subproblem which is a continuous optimization problem. The master problem and subproblem are solved iteratively and coordinated via Benders cuts, which inform the former about the effect of the complicating variables on the latter. Although GBD has been applied for the solution of mixed integer MPC problems, its convergence can be slower than a given computational budget. Recently, Machine Learning (ML) has been used to reduce the solution time of MIP problems that arise in mixed integer MPC applications by approximating the values of the binary variables and active constraints, thus reducing the MIP problem to a continuous optimization problem, or by warm-starting the solver [12-14].

In this paper, we aim to reduce the computational time related to the solution of the master problem and subproblem, thus enabling the efficient online solution of mixed integer MPC problems using GBD. We propose an ML-based branch and check GBD algorithm, where the master problem is solved once using branch and check, and machine learning is used to approximate online the necessary information for constructing the Benders cuts whenever an integer feasible solution is found during branch and check. This approach alleviates the need to solve the master problem and subproblem multiple times online. The proposed algorithm can be applied to a broad class of problems that arise in mixed integer MPC applications, such as Mixed Integer Linear (MILP), Quadratic (MIQP), and Nonlinear (MINLP) programming problems.

The proposed approach is applied to an economic mixed integer MPC problem. Specifically, we consider an isothermal CSTR where five products are manufactured, and an economic MPC problem is formulated to determine the production sequence while considering the dynamic behavior of the system, given the price, demand, and production cost for every product. We generate 20 random instances of the problem, assuming that the price and demand follow a uniform distribution, and compare the proposed algorithm with the standard application of GBD as proposed in [13]. The numerical results show that the proposed algorithm leads to a 94 % reduction in solution time, compared to standard GBD, while the percentage error, due to the approximation of the Benders cut, is less than 0.04%.

References:

[1]. Deng, Kun, Yu Sun, Sisi Li, Yan Lu, Jack Brouwer, Prashant G. Mehta, MengChu Zhou, and Amit Chakraborty. "Model predictive control of central chiller plant with thermal energy storage via dynamic programming and mixed-integer linear programming." IEEE Transactions on Automation Science and Engineering 12, no. 2 (2014): 565-579.

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

[3]. McAllister, R.D. and Rawlings, J.B., 2022, June. Advances in mixed-integer model predictive control. In 2022 American Control Conference (ACC) (pp. 364-369). IEEE.

[4]. Hespanhol, P., Quirynen, R. and Di Cairano, S., 2019, June. A structure exploiting branch-and-bound algorithm for mixed-integer model predictive control. In 2019 18th European Control Conference (ECC) (pp. 2763-2768). IEEE.

[5]. Tawarmalani, M. and Sahinidis, N.V., 2005. A polyhedral branch-and-cut approach to global optimization. Mathematical programming, 103(2), pp.225-249.

[6]. Oberdieck, R. and Pistikopoulos, E.N., 2015. Explicit hybrid model-predictive control: The exact solution. Automatica, 58, pp.152-159.

[7]. Axehill, D., Besselmann, T., Raimondo, D.M. and Morari, M., 2014. A parametric branch and bound approach to suboptimal explicit hybrid MPC. Automatica, 50(1), pp.240-246.

[8]. Mohideen, M.J., Perkins, J.D. and Pistikopoulos, E.N., 1997. Towards an efficient numerical procedure for mixed integer optimal control. Computers & Chemical Engineering, 21, pp.S457-S462.

[9]. Mitrai, I. and Daoutidis, P., 2022. An adaptive multi-cut decomposition based algorithm for integrated closed loop scheduling and control. In Computer Aided Chemical Engineering (Vol. 49, pp. 475-480). Elsevier.

[10]. Masti, D., Pippia, T., Bemporad, A. and De Schutter, B., 2020. Learning approximate semi-explicit hybrid MPC with an application to microgrids. IFAC-PapersOnLine, 53(2), pp.5207-5212.

[11]. Cauligi, A., Culbertson, P., Schmerling, E., Schwager, M., Stellato, B. and Pavone, M., 2021. Coco: Online mixed-integer control via supervised learning. IEEE Robotics and Automation Letters, 7(2), pp.1447-1454.

[12]. Mitrai, I., and Daoutidis, P., “Learning to initialize generalized benders decomposition via active learning,” in FOCAPO/CPC, San Antonio, Texas, 2023

[13]. Mitrai, I. and Daoutidis, P., 2022. A multicut generalized benders decomposition approach for the integration of process operations and dynamic optimization for continuous systems. Computers & Chemical Engineering, 164, p.107859.