Slide 1

A MIP Code is a Bag of Tricks

Typical Path to Widespread Adoption of a New Technique

A Few Examples
[Bixby, Fenelon, Gu, Rothberg, Wunderling, 2002]

Unlikely Path to Widespread Adoption of a New Technique

Another Unlikely Path to Widespread Adoption of a New Technique

Example : Probing
[Brearley, Mitra, Williams, 1975]

Model mod011.mps without probing

Model mod011.mps with probing

Probing on a Wider Set of Models

Another Example : Strong Branching
[Applegate, Bixby, Chvatal, and Cook, 1995]

Strong Branching on a Wider Set of Models

Consistency Between
User Goals and Code Goals

A MIP Code Has An (Implicit) Emphasis

Potential Mismatch Between Goals

Performance for Feasibility Emphasis

User Emphasis Setting:
Feasibility Instead of Optimality

User Emphasis Setting in 8.0

Performance for Feasibility Emphasis

MIP Results of CPLEX8.0
[Bixby, Fenelon, Gu, Rothberg, Wunderling, 2002]

Hard Problems

Exploiting User Knowledge

User Knowledge

Advanced Features

Adding User Cuts or Lazy Constraints

Caution: User Cuts

Caution: Lazy Constraints

Side Constraints

Side Constraints

Handling Side Constraints - Linearize

Handling Side Constraints - Branching

Tighter Implicit Formulation?

Gomory Cut Review

An Important Class: Disjunctive Constraints

Cardinality Constraint

Gomory Cut Extension (with Puget)

One Size Fits All?