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.

本文介绍了在 2021 年 NeurIPS 机器学习求解组合优化问题比赛中，qqy 团队的胜出方案 Yordle。该方案是一种高效的模仿学习框架，用于改进分支定界算法的性能，并通过数据采样和筛选提高准确率。在实验中，Yordle 的性能显著优于竞赛所采用的基准算法，且需要更少的数据和时间来训练决策模型。

Yordle: 分支定界高效模仿学习

Yordle: An Efficient Imitation Learning for Branch and Bound

Deep Neural Networks can generalize despite being significantly
overparametrized. Recent research has tried to examine this phenomenon from
various view points and to provide bounds on the generalization error or
measures predictive of the generalization gap based on these viewpoints, such
as norm-based, PAC-Bayes based, and margin-based analysis. In this work, we
provide an interpretation of generalization from the perspective of quality of
internal representations of deep neural networks, based on neuroscientific
theories of how the human visual system creates invariant and untangled object
representations. Instead of providing theoretical bounds, we demonstrate
practical complexity measures which can be computed ad-hoc to uncover
generalization behaviour in deep models. We also provide a detailed description
of our solution that won the NeurIPS competition on Predicting Generalization
in Deep Learning held at NeurIPS 2020. An implementation of our solution is
available at this https URL

从神经科学理论的角度解释深度神经网络的泛化能力，提供可自主计算的复杂度度量方法以揭示深度模型的泛化行为，并详细介绍在 NeurIPS 2020 举办的预测深度学习泛化比赛中获胜的解决方案。