标题： 分支定界 versus 抬升投影松弛在组合优化中的比较 显示英文标题

标题： Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

摘要： 本文中，我们考虑了一种理论框架来比较分支定界法与经典的提升和投影层次结构。 我们简化了对分支定界法定义的优化分析。 我们引入了“偏斜$k$-树”，这提供了一个与 Sherali-Adams 不可比较的松弛层次，并且我们证明对于某些实例它要好得多。 我们还给出了一个例子，在其中提升和投影方法表现非常好而分支定界法则不然。 最后，我们研究了高度不超过$k$的分支定界树集，并有效地在这两种著名的提升和投影过程之间“挤压”了它们的效果。 显示英文摘要

摘要： In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce "skewed $k$-trees" which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also give an example where lift-and-project does very well and branch-and-bound does not. Finally, we study the set of branch-and-bound trees of height at most $k$ and effectively "squeeze" their effectiveness between two well-known lift-and-project procedures.