Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

• 成果类型: Article; Early Access
• 署名作者: Cornuejols, Gerard; Dubey, Yatharth
• 署名单位: Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02248-7
• 发表日期: 2025
• 关键词: Hierarchy

摘要

In this note, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis by 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 squeeze their effectiveness between two well-known lift-and-project procedures.