Optimization Online


Shaping and Trimming Branch-and-bound Trees

Philipp M. Christophel(philipp.christophel***at***sas.com)
Imre Polik(imre***at***polik.net)

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.

Keywords: dynamic trees, tree reorganization

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Optimization Software and Modeling Systems (Optimization Software Design Principles )

Citation: Technical report

Download: [PDF]

Entry Submitted: 09/05/2017
Entry Accepted: 09/05/2017
Entry Last Modified: 09/05/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society