(206e) Learning to Select Convex Relaxations in a Branch and Bound Algorithm

Mixed-integer linear and nonlinear programming have wide applications in PSE¹. Until recently, its methods have focused on solving problem instances in isolation, ignoring that they often stem from related data distributions in practice. However, recent years have seen a surge of interest in using machine learning as a new approach for solving MILP problems², either directly as solvers or by enhancing exact solvers. Examples include learning to select branching variables in a branch and bound algorithm^3,4, learning to schedule primal heuristics⁵, learning to decompose a problem⁶, and learning to select cutting planes⁷. In this presentation, we focus on an important task in solving nonconvex MINLP problems, selecting convex relaxations in a branch and bound algorithm. Global MINLP solvers such as BARON⁸ and ANTIGONE⁹ rely on creating convex relaxations for the nonconvex functions. However, which convex relaxation to use at each node for a given problem is not straightforward. On the contrary, tradeoffs usually exist for using different relaxations. Tight relaxations are typically expensive to solve but can reduce the number of nodes in a branch and bound algorithm. Using weaker relaxations allows us to enumerate more nodes within a time limit but will increase the total number of nodes needed to prove optimality.

In this presentation, we use Quadratic Unconstrained Binary Optimization(QUBO) as a proof-of-concept for learning to select convex relaxations. SDP type of relaxations provides tight bounds¹⁰ for QUBO but are more expensive to solve than most LP relaxations. We propose a hybrid branch and bound framework¹¹ for solving QUBOs. By default, only the LP relaxation based on McCormick inequalities is solved at each node of the branch-and-bound algorithm. SDP relaxations that include the McCormick inequalities are solved parsimoniously, i.e., we only wish to solve the SDP relaxations if there is a high chance that it can fathom a given node. To predict whether a node can be fathomed by SDP bound, we propose a machine learning-based method that includes features associated with each branch and bound node. The most important feature is the objective of solving a convex quadratic constrained program (QCP) that is derived by fixing most of the variables at a node to the optimal solution of its parent node and taking the Schur complement. The QCP problem has O(n) variables, making it computationally much easier to solve than the original SDP. Other features such as the depths of the node and the density of the adjacency matrix are also used. A support vector machine classifier is trained which achieves over 95% accuracy in predicting whether the SDP bound can fathom a node. Our proposed approach is shown to save the number of SDP solves and computational time in a number of maxcut instances with different sizes and densities we tested.

1. Biegler, L. T. & Grossmann, I. E. Retrospective on optimization. Comput Chem Eng 28, 1169–1192 (2004).
2. Bengio, Y., Lodi, A. & Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 290, 405–421 (2021).
3. Balcan, M.-F., Dick, T., Sandholm, T. & Vitercik, E. Learning to Branch. in ICML (eds. Dy, J. G. & Krause, A.) vol. 80 353–362 (PMLR, 2018).
4. Ghaddar, B. et al. Learning for Spatial Branching: An Algorithm Selection Approach. arXiv preprint arXiv:2204.10834(2022).
5. Khalil, E. B., Dilkina, B., Nemhauser, G., Ahmed, S. & Shao, Y. Learning to Run Heuristics in Tree Search. in 26th International Joint Conference on Artificial Intelligence (IJCAI) (2017).
6. Mitrai, I., Tang, W. & Daoutidis, P. Stochastic blockmodeling for learning the structure of optimization problems. AIChE Journal 68, (2022).
7. Baltean-Lugojan, R., Bonami, P., Misener, R. & Tramontani, A. Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. preprint: http://www. optimization-online. org/DB_ HTML/2018/11/6943. html (2019).
8. Kılınç, M. R. & Sahinidis, N. V. Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON. Optim Methods Softw 33, 540–562 (2018).
9. Misener, R. & Floudas, C. A. ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations. Journal of Global Optimization 59, 503–526 (2014).
10. Rendl, F., Rinaldi, G. & Wiegele, A. Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations. Math Program 121, 307–335 (2010).
11. Furini, F. & Traversi, E. Hybrid SDP Bounding Procedure. in 248–259 (2013). doi:10.1007/978-3-642-38527-8_23.