Progress in Linear
Programming Based Branch-and-Bound Algorithms
Objectives
Outline
Mixed 0-1 Integer
Programming
Why Use MIP ?
Applicability
Recent Applications
Transportation planning and
operations
Facility location
Production scheduling
Supply-chain management
LP Based Branch and Bound
LP Based Branch and Bound
How to improve performance?
Formulations
Uncapacitated Facility
Location
Uncapacitated Facility
Location
Uncapacitated Facility
Location
Parallel Machine Scheduling
Parallel Machine Scheduling
Parallel Machine Scheduling
Parallel Machine Scheduling
Branching Strategies
Variable Selection
Prediction Methods
Estimation Methods
Lower Bounding
Combining Estimation and
Lower Bounding
Using Predictors
Node Selection
Node Selection Methods
Static Methods
Static Methods
Estimate-based Methods
Estimate-based Methods
Two-phase Methods
Two-phase Methods
Two-phase Methods
Backtracking Methods
Preprocessing and Probing
Detecting Infeasibility
Detecting Infeasibility
Detecting Infeasibility
Probing
Fixing Variables
Fixing Variables
Fixing Variables
Identifying logical
implications
Identifying logical
implications
Diving Heuristic
Diving Heuristic
Local Branching
Local Branching
Slide 54
Slide 55
Slide 56