.png){kind=icon}
.png){kind=icon}
Return
Adaptive solution prediction for combinatorial optimization
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2023.01.054.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 vari-ables. However, acquiring such features is challenging due to the high complexity of COPs. This paper pro-poses 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 em-ploy 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 im-proves 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.(c) 2023 Elsevier B.V. All rights reserved.
Keywords:
Combinatorial optimization
Machine learning
Column generation
Branch-and-price
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W