论文标题
参数化分支和结合搜索树以学习分支策略
Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
论文作者
论文摘要
Branch and Bound（B＆B）是通常用于解决混合企业线性编程问题（MILP）的确切树搜索方法。 MILP的学习分支政策已成为一个活跃的研究领域，大多数作品都建议模仿强大的分支规则，并将其专门针对不同的问题。相反，我们旨在学习一项跨越异构MILP的策略：我们的主要假设是，将B＆B搜索树状态的参数化可以帮助这种类型的概括。我们提出了一个新颖的模仿学习框架，并引入了新的输入功能和体系结构来代表分支。 MILP基准实例的实验清楚地表明了将搜索树状态明确参数化的优点，以更高的准确性和较小的B＆B树来调节分支决策。由此产生的策略明显优于当前“学习分支”的最新方法，通过有效地允许概括性地看不见的实例。
Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs). Learning branching policies for MILP has become an active research area, with most works proposing to imitate the strong branching rule and specialize it to distinct classes of problems. We aim instead at learning a policy that generalizes across heterogeneous MILPs: our main hypothesis is that parameterizing the state of the B&B search tree can aid this type of generalization. We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching. Experiments on MILP benchmark instances clearly show the advantages of incorporating an explicit parameterization of the state of the search tree to modulate the branching decisions, in terms of both higher accuracy and smaller B&B trees. The resulting policies significantly outperform the current state-of-the-art method for "learning to branch" by effectively allowing generalization to generic unseen instances.
