Yordle: An Efficient Imitation Learning for Branch and Bound
This work addresses the challenge of enhancing heuristic components in combinatorial optimization solvers for researchers and practitioners, though it is incremental as it builds on existing imitation learning approaches.
The authors tackled the problem of improving Branch and Bound solvers for combinatorial optimization by developing Yordle, an efficient imitation learning framework that uses hybrid sampling and data selection methods, achieving around 50% higher score than the baseline while using only 1/4 of the data.
Combinatorial optimization problems have aroused extensive research interests due to its huge application potential. In practice, there are highly redundant patterns and characteristics during solving the combinatorial optimization problem, which can be captured by machine learning models. Thus, the 2021 NeurIPS Machine Learning for Combinatorial Optimization (ML4CO) competition is proposed with the goal of improving state-of-the-art combinatorial optimization solvers by replacing key heuristic components with machine learning techniques. This work presents our solution and insights gained by team qqy in the dual task of the competition. Our solution is a highly efficient imitation learning framework for performance improvement of Branch and Bound (B&B), named Yordle. It employs a hybrid sampling method and an efficient data selection method, which not only accelerates the model training but also improves the decision quality during branching variable selection. In our experiments, Yordle greatly outperforms the baseline algorithm adopted by the competition while requiring significantly less time and amounts of data to train the decision model. Specifically, we use only 1/4 of the amount of data compared to that required for the baseline algorithm, to achieve around 50% higher score than baseline algorithm. The proposed framework Yordle won the championship of the student leaderboard.