论文标题
压缩分支和围成的树木
Compressing Branch-and-Bound Trees
论文作者
论文摘要
分支机构（BB）树对整数程序的值进行了双重绑定。在这项工作中，我们介绍了树木压缩问题（TCP）：给定证明双重绑定的BB树T，我们可以通过（1）在t或（2）中删除t的某些节点上应用不同的分离的较小树（或更强）绑定的较小树？我们认为，对BB树的事后分析可能有助于确定BB算法中有用的一般析取。我们通过考虑计算复杂性和TCP的局限性来启动研究。然后，我们使用精确的和启发式压缩算法来评估通常使用的分支策略产生的现实分支和结合树的可压缩性。
A branch-and-bound (BB) tree certifies a dual bound on the value of an integer program. In this work, we introduce the tree compression problem (TCP): Given a BB tree T that certifies a dual bound, can we obtain a smaller tree with the same (or stronger) bound by either (1) applying a different disjunction at some node in T or (2) removing leaves from T? We believe such post-hoc analysis of BB trees may assist in identifying helpful general disjunctions in BB algorithms. We initiate our study by considering computational complexity and limitations of TCP. We then conduct experiments to evaluate the compressibility of realistic branch-and-bound trees generated by commonly-used branching strategies, using both an exact and a heuristic compression algorithm.
