(15f) Taking the Human out of the Decomposition-Based Optimization Loop Via Artificial Intelligence and Network Science
AIChE Annual Meeting
2023
2023 AIChE Annual Meeting
Computing and Systems Technology Division
CAST Director's Student Presentation Award Finalists (Invited Talks)
Monday, November 6, 2023 - 2:00pm to 2:18pm
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