Yordle: An Efficient Imitation Learning for Branch and Bound
  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.
