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

2023/10/31 by Gérard Cornuéjols, Cornuéjols, Gérard, Yatharth Dubey +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Packing Problems

paper · pdf · doi:10.48550/arxiv.2311.00185

openalex publication_date 2023/10/31 · openalex created_date 2023/11/03 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
• Shaping and Trimming Branch-and-bound Trees
• On optimizing over lift-and-project closures
• The Branch-and-Bound Tree Closure
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II