Branch-and-Cut

Branch-and-Cut

Branch-and-Cut

Cut Classification

Cut Classification

Cut Classification

Cut Classification

Lift-and-Project cuts

Lift-and-Project cuts

Slide 10

Slide 11

Slide 12

Slide 13

Slide 14

Slide 15

Slide 16

Slide 17

How do we get disjunctive cuts in practice?

Approach

Relaxation Cuts

Cover Inequalities

Separation

Separation

Lifting

Lifting

Lifting

Lifting

Lifting

Sequential Lifting

Continuous 0-1 Knapsack

Node Packing Relaxation

Node Packing Relaxation

Cut generation

Cut Management

Cut Management

Cut Management

Cut Management

Cut Management

Cut Management

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Branch-and-Price

Branch-and-Price

Branch-and-Price

Branch-and-Price

Why use formulations with a huge number of variables ?

Complications

Generalized Assignment Problem

GAP

Natural Formulation

Column Generation Formulation

Column Generation Formulation

Advantage

Solving LP Relaxation

Pricing Problem

Pricing Problem

Branching

Branching