(61y) Learning to Select the Best Optimization Solution Strategy: An Algorithm Selection Approach

Decision-making optimization problems arise in a wide range of applications in chemical engineering, ranging from the molecular to the enterprise scale [1,2]. Many methods have been developed for the solution of broad classes of optimization problems, such as Mixed Integer Linear (MILP), Nonlinear (NLP), and Mixed Integer Nonlinear (MINLP) Programming problems [3-5]. Despite these significant advances, not a single algorithm outperforms all others for all problems. Therefore, given an optimization problem, it is challenging to determine a–priori which solution strategy, i.e., solver, solves the problem in the minimum computational time or finds a high-quality feasible solution for a given computational budget.

This problem can be cast as an algorithm selection problem [6] in which given an optimization problem P and a set of algorithms {α₁,...,α_n} one must find the algorithm α^* that optimizes some performance function m (such as the solution time). This is a black box optimization problem since the solution time for a given problem is not known a-priory. Algorithm selection methods have been applied to optimization problems, using Machine Learning (ML) to either develop a surrogate model of the performance function or approximate the solution of the algorithm selection problem itself [6-9]. These methods have used a handcrafted vectorial feature representation of the optimization problem (such as the number of variables and constraints, numerical conditioning indexes, etc.), which becomes the input to the machine learning model. This approach aggregates information about the problem and does not consider the exact structural and functional coupling among the variables and the constraints of a problem.

In this paper, we propose a new framework for selecting the best solution strategy for generic optimization problems while considering the detailed structural and functional interaction between the variables and the constraints of the problem. Specifically, we exploit geometric deep learning and pose the algorithm selection problem as a graph classification task. We represent an optimization problem as a graph [10,11], where the nodes represent variables and constraints, and the edges capture the presence of a variable in a constraint. This representation captures the structural coupling among the variables and the constraints through the adjacency matrix A. We extend this representation by incorporating a set of features for every node and edge in the graph, which capture key information about the variables and constraints, such as variable domain and convexity. Concatenation of all the features forms a feature matrix F, which captures the functional coupling among the variables and the constraints. Given this representation, we use graph neural networks [12] to develop a graph classifier C, where the inputs are the feature and adjacency matrices (A, F) and the output is a vector p, where p_i is the probability that algorithm α_i solves the problem in the minimum CPU time. Finally, we show how the classifiers obtained by the proposed approach can be integrated with current state-of-the-art optimization technology to enable full automation of the proposed approach.

For illustration, we use the proposed framework to learn a classifier that predicts the best solution strategy for convex MINLP problems. We use benchmark MINLPs for learning a graph classifier, which determines if a convex MINLP should be solved by the branch and bound or the outer approximation algorithm as implemented in BONMIN 1.8.8 [13]. The results show that the classifier has 90% accuracy on the testing set.

References:

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

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

[3]. 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, pp.25-57.

[4]. Misener, R. and Floudas, C.A., 2014. ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. Journal of Global Optimization, 59(2-3), pp.503-526.

[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]. Kerschke, P., Hoos, H.H., Neumann, F. and Trautmann, H., 2019. Automated algorithm selection: Survey and perspectives. Evolutionary computation, 27(1), pp.3-45.

[7]. Hutter, F., Xu, L., Hoos, H.H. and Leyton-Brown, K., 2014. Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence, 206, pp.79-111.

[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]. Bonami, P., Lodi, A. and Zarpellon, G., 2022. A classifier to decide on the linearization of mixed-integer quadratic problems in CPLEX. Operations Research, 70(6), pp.3303-3320.

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

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

[12]. Kipf, T.N. and Welling, M., 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.

[13]. Bonami, P., Biegler, L.T., Conn, A.R., Cornuéjols, G., Grossmann, I.E., Laird, C.D., Lee, J., Lodi, A., Margot, F., Sawaya, N. and Wächter, A., 2008. An algorithmic framework for convex mixed integer nonlinear programs. Discrete optimization, 5(2), pp.186-204.