On Generalized Branching Methods for Mixed Integer Programming

Organization

Problem Formulation

Approaches to Branching

 An Example

Matter of Definitions

Example (continued)

 An Example (continued)

Lenstra’s Algorithm

Lenstra’s Algorithm (continued)

Lenstra’s Algorithm (Geometry)

 Pervious Work

Issues

Adjoint Lattice

Branching Hyperplane finding Problem

Find An integral Adjoint Basis

Ellipsoidal Approximation

The Quality of Approximation

Bound on Minimum Width Using Ellipsoidal Approximation

How to Solve Minimum Width Problems

Lovasz and  Scarf Basis

An interpretation of the Aardal, Hurkens and Lenstra Reformulation

Mixed Integer Programming

Mixed Integer Problem

Generalized B&B Method

Knapsack Test Problems

Numerical Results on Hard Knapsack Problems

Market Split Problems

Larger Market Split Problems

 # of LLL iterations and GBB Tree Size

Conclusions