Shaping and Trimming Branch-and-bound Trees

2017/09/05 by Philipp M. Christophel, Christophel, Philipp M., Imre Pólik +1
Computer Science · Mathematics · #Commutative Algebra and Its Applications #FOS: Mathematics #Formal Methods in Verification #Logic, programming, and type systems #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1709.01583

openalex publication_date 2017/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a new branch-and-bound type search method for mixed integer linear optimization problems based on the concept of offshoots (introduced in this paper). While similar to a classic branch-and-bound method, it allows for changing the order of the variables in a dive (shaping) and removing unnecessary branching variables from a dive (trimming). The regular branch-and-bound algorithm can be seen as a special case of our new method. We also discuss extensions to our new method such as choosing to branch from the top or the bottom of an offshoot. We present several numerical experiments to give a first impression of the potential of our new method.

Related

• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Narrow Gauge and Analytical Branching Strategies for Mixed Integer Programming
• Complexity of branch-and-bound and cutting planes in mixed-integer optimization -- II
• The Branch-and-Bound Tree Closure
• Target oriented branch & bound method for global optimization