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