Adaptive solution prediction for combinatorial optimization

Keywords Combinatorial optimization; Machine learning; Column generation; Branch-and-price Highlights * Adaptive solution prediction is proposed for heuristic search, based on an offline-trained ML model to predict the optimal solution iteratively. * Information is extracted from improved solutions in online sampling and used as features in an ML model, enabling adaptive solution prediction. * Adaptive solution prediction benefits from both online and offline learning, hence it can find heuristic solutions effectively and efficiently. * Adaptive solution prediction can find many high-quality solutions, making it advantageous for heuristic pricing in branch-and-price. Abstract This paper aims to predict optimal solutions for combinatorial optimization problems (COPs) via machine learning (ML). To find high-quality solutions efficiently, existing work uses a ML prediction of the optimal solution to guide heuristic search, where the ML model is trained offline under the supervision of solved problem instances with known optimal solutions. To predict the optimal solution with sufficient accuracy, it is critical to provide a ML model with adequate features that can effectively characterize decision variables. However, acquiring such features is challenging due to the high complexity of COPs. This paper proposes a framework that can better characterize decision variables by harnessing feedback from a heuristic search over several iterative steps, enabling an offline-trained ML model to predict the optimal solution in an adaptive manner. We refer to this approach as adaptive solution prediction (ASP). Specifically, we employ a set of statistical measures as features, which can extract useful information from feasible solutions found by a heuristic search and inform the ML model as to which value a decision variable is likely to take in high-quality solutions. Our experiments on three NP-hard COPs show that ASP substantially improves the prediction quality of an offline-trained ML model and achieves competitive results compared to several heuristic methods in terms of solution quality. Furthermore, we demonstrate that ASP can be used as a heuristic-pricing method for column generation, to boost an exact branch-and-price algorithm for solving the graph coloring problem. Author Affiliation: (a) School of Computing Technologies, RMIT University, Melbourne, Australia (b) La Trobe Business School, La Trobe University, Melbourne, Australia (c) School of Science, RMIT University, Melbourne, Australia (d) School of Mathematics, Monash University, Melbourne, Australia * Corresponding author. Article History: Received 28 February 2022; Accepted 25 January 2023 Byline: Yunzhuang Shen [s3640365@student.rmit.edu.au] (*,a), Yuan Sun [yuan.sun@latrobe.edu.au] (b), Xiaodong Li [xiaodong.li@rmit.edu.au] (a), Andrew Eberhard [andy.eberhard@rmit.edu.au] (c), Andreas Ernst [andreas.ernst@monash.edu] (d)