(15f) Taking the Human out of the Decomposition-Based Optimization Loop Via Artificial Intelligence and Network Science

Chemical engineering is confronting major challenges such as the decarbonization of the energy sector and the chemical industry, the design of sustainable production processes, and the operation of resilient supply chain networks [1-3]. These challenges involve decision-making at multiple temporal and spatial scales, leading to large-scale optimization problems that typically cannot be solved monolithically. Decomposition-based methods can solve such problems efficiently by exploiting the underlying interaction pattern (structure) between the variables and constraints of the problem and decomposing it into a number of easier-to-solve subproblems [4]. However, the implementation of decomposition-based solution is challenging. First, these methods require a decomposition of the problem itself. However, the underlying structure of the problem is not always apparent. Secondly, the corresponding solution algorithms have many steps which affect strongly their computational performance . The configuration of these steps, such as the initialization, is nontrivial . Finally, the advantage of decomposition-based solution methods over monolithic ones for a given problem is not known a-priory. Over the last few years, there has been some progress in addressing the above challenges individually, for specific classes of problems. We note for example, previous work in our group to generate high quality decompositions using block structure detection [5,6], or recent attempts to use Artificial Intelligence (AI) and Machine Learning (ML) to accelerate optimization algorithms for mixed integer linear programming problems [7-10].

In this work, we propose an overarching conceptual framework and an automated workflow for addressing the above challenges for generic mixed integer nonlinear programming problems (MINLPs). The proposed framework and toolbox, called Learning to Decompose (L2D), combines network science, optimization theory, and machine learning to determine: (i) how to decompose an optimization problem, (ii) how to initialize the solution algorithm for the decomposed problem, and (iii) when to apply a decomposition-based solution algorithm over a monolithic one. On the first task, stochastic blockmodeling [11] is used to “learn” the underlying structure of an optimization problem based on appropriate network representations of the problem. The learned structure is linked to the appropriate distributed or hierarchical decomposition-based solution method. On the second task, active learning [12] is used to efficiently learn a surrogate model that approximates the effect of the algorithm configuration on the solution time. This surrogate is used to select the best configuration of the decomposition-based solution algorithm. Finally, on the third task, a graph classification approach is developed to determine a-priori if a decomposition-based solution should be implemented over a monolithic one. The graph classification approach decides whether a decomposition-based solution method should be used by considering the detailed structural and functional interaction between the variables and the constraints of the problem.

The proposed framework is applied to multiple case studies, including the solution of benchmark MINLP problems and mixed integer economic model predictive control problems.

References:

[1]. Engineering National Academies of Sciences and Medicine. New directions for chemical engineering. 2022

[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]. Pistikopoulos, E.N., Barbosa-Povoa, A., Lee, J.H., Misener, R., Mitsos, A., Reklaitis, G.V., Venkatasubramanian, V., You, F. and Gani, R., 2021. Process systems engineering–the generation next?. Computers & Chemical Engineering, 147, p.107252.

[4]. Conejo, A.J., Castillo, E., Minguez, R. and Garcia-Bertrand, R., 2006. Decomposition techniques in mathematical programming: engineering and science applications. Springer Science & Business Media.

[5]. Allman, A., Tang, W. and Daoutidis, P., 2019. DeCODe: a community-based algorithm for generating high-quality decompositions of optimization problems. Optimization and Engineering, 20, pp.1067-1084.

[6]. Mitrai, I., Tang, W. and Daoutidis, P., 2022. Stochastic blockmodeling for learning the structure of optimization problems. AIChE Journal, 68(6), p.e17415.

[7]. Bengio, Y., Lodi, A. and Prouvost, A., 2021. Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 290(2), pp.405-421.

[8]. Kruber, M., Lübbecke, M.E. and Parmentier, A., 2017. Learning when to use a decomposition. In Integration of AI and OR Techniques in Constraint Programming: 14th International Conference, CPAIOR 2017, Padua, Italy, June 5-8, 2017, Proceedings 14 (pp. 202-210). Springer International Publishing.

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

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

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

[12]. B. Settles, “Active learning literature survey,” Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009