论文标题
Yordle：有效的分支学习和约束的模仿学习
Yordle: An Efficient Imitation Learning for Branch and Bound
论文作者
论文摘要
组合优化问题由于其巨大的应用潜力引起了广泛的研究兴趣。在实践中，在解决组合优化问题的过程中存在高度冗余的模式和特征，可以通过机器学习模型来捕获它们。因此，提出了2021个用于组合优化（ML4CO）竞争的神经机器学习，目的是通过用机器学习技术替换关键的启发式组件来改善最先进的组合优化求解器。这项工作介绍了我们的解决方案和QQY团队在比赛的双重任务中获得的见解。我们的解决方案是一个高效的模仿学习框架，用于提高分支和绑定（B＆B）的绩效，名为Yordle。它采用混合采样方法和有效的数据选择方法，不仅可以加速模型训练，而且可以提高分支变量选择期间的决策质量。在我们的实验中，Yordle极大地胜过竞争采用的基线算法，同时需要较小的时间和数据量来训练决策模型。具体而言，与基线算法所需的数据相比，我们仅使用1/4的数据量，以达到比基线算法高约50％。拟议的框架Yordle赢得了学生排行榜的冠军。
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.
