Scholarlink

<p>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 <i>k</i>-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 <i>k</i> and “squeeze” their effectiveness between two well-known lift-and-project procedures.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年7月1日

查看全文
  • Gérard Cornuéjols,
  • Yatharth Dubey

摘要

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.