ORSUM NB

Download
Share  Add to  Flag Embed
Uploaded from authorPOINTLite
Views:
 
Category: Entertainment
     
 
License:   All Rights Reserved

Presentation Description

No description available.

Comments

 

By: shahingelareh (41 month(s) ago)

Hi, Thank you very much. That is great! May I access the slides to print it out?

Presentation Transcript

Column Generation: Theory, Algorithms and Applications: 

Column Generation: Theory, Algorithms and Applications Dr Natashia Boland Department of Mathematics and Statistics The University of Melbourne

Outline: 

Outline  Linear and integer programs  A shipping problem: column generation formulation  Column generation and why it works  Successful applications  Difficulties  Towards a cure: duality  A general framework for stabilisation  Progress in column generation and the future

Linear Programs: 

Linear Programs xi = ith decision variable, i = 1,…,n min c1x1 + c2x2 +…+ cnxn s.t. a11x1 + a12x2 +…+ a1nxn  b1 a21x1 + a22x2 +…+ a2nxn  b2 am1x1 + am2x2 +…+ amnxn  bm xi integer, i = 1,…,n Integer

A Shipping Problem*: 

A Shipping Problem*  Delivering product to customers around the world  Shipping contracts entered into for next 12 months  Contract specifies ship s can be used at most once in any ms consecutive months – the spread  Contract specifies min and max limits on number of times ship used over year Operations Research Group Pty Ltd J. Horton, T. Surendonk, E. Jago * See Boland and Surendonk, 2001

Exercising a Shipping Contract: 

Exercising a Shipping Contract Jan Feb Mar Apr May Jun Jul Aug Sep Spread = 3 months Spread = 4 months CUSTOMER DEMAND

Exercising a Shipping Contract: 

Exercising a Shipping Contract Jan Feb Mar Apr May Jun Jul Aug Sep Spread = 3 months Spread = 4 months CUSTOMER DEMAND 1 2 X

An Integer Programming Model: 

An Integer Programming Model xist = 1, if ship s delivers to customer i in period t 0, otherwise min  costisxist i,s,t s.t.

Contract Constraints: 

Contract Constraints i, t mins   xist  maxs For each ship s for all t=1,… spread of ms periods

Outcomes: 

Outcomes  Implemented using top-grade commercial integer programming solver (ILOG Cplex)  16 customers, about 30 ships  Ran for many hours – out of memory  Best solution found might be as bad as 16% from optimal WHAT’S GOING WRONG?

Integrality Gap: 

Integrality Gap Integer program min cx s.t. Ax  b x  {0,1}n Value of integer program >> Value of relaxation Linear programming relaxation min cx s.t. Ax  b 0  x  1

Re-formulation: Ship Combinations: 

Re-formulation: Ship Combinations Jan Feb Mar Apr May Jun Jul Aug Sep Which combination of ships should be used to meet customer i’s demand in period t?

A Column Generation Model: 

A Column Generation Model yikt = 1, if combination k used for customer i in period t 0, otherwise For k  Kit

The Model: 

The Model min  ( costis)yikt i,t,kKit  yikt = 1 k Kit s.t. sk customer i demand met in period t  (yikt + yik(t+1) + … + yik(t+ms-1) )  1 i,k: s k contract constraints for ship s for all t=1,…

Issues: 

Issues  There are a very large number of variables - how can we solve even the linear programming relaxation?  Why will this reformulation help? ANSWERS: Column generation The linear program better approximates the integer program - WHY?

Column Generation: 

Column Generation 1. Select a small number of variables and solve the linear program using only these. 2. Find an unused variable which, if included, would most improve the objective value, or determine that there is none - the linear program has been solved: stop. 3. Include the variable in the linear program, re-solve it, and go to step 2.  Model this as an optimization problem Solve the column generation subproblem

The Shipping Subproblem: 

The Shipping Subproblem For each customer i and period t, find a combination of ships that will most improve the objective: vs = 1, if ship s used in combination 0, otherwise min  f(costis,s)vs s.t.

Shipping Column Generation: 

Shipping Column Generation 1. Select a small number of combinations for each customer and period. Solve the linear program using only these. 2. For each customer and period, solve the shipping subproblem: if its value < cut-off include the optimal combination in the linear program. 3. If no new combinations included in step 2, the linear program has been solved: stop. 4. Re-solve the linear program and go to step 2.

Outcomes: 

Outcomes  Implemented using ILOG Cplex (and AMPL)  Solved in less than 2 minutes  Step 2 performed 34 times  1700 combinations generated  Solution to linear program was integer optimal WHAT’S GOING RIGHT?!

Dantzig-Wolfe Decomposition: 

Dantzig-Wolfe Decomposition Integer program min cx s.t. Ax  b Dx  g x  {0,1}n Value integer program >> Value linear relaxation Value integer program  Value D-W decomposition 

Slide20: 

Geometry

Successful Applications: A Brief History: 

Successful Applications: A Brief History Cutting stock problems Air crew scheduling Aircraft fleeting and routing Crew rostering Vehicle routing Global shipping Multi-item lot-sizing Optical telecommunications network design Cancer radiation treatment using IMRT      1960 1980 1990 2000

Difficulties with Column Generation: 

Difficulties with Column Generation  Tailing off – slow convergence  Getting integrality – column generation within branch-and-bound and in combination with cutting planes  Columns with set-up costs

Difficulties with Column Generation: 

Difficulties with Column Generation  Tailing off – slow convergence  Getting integrality – column generation within branch-and-bound and in combination with cutting planes  Columns with set-up costs

A Dual Approach: 

A Dual Approach Integer program min cx s.t. Ax = b Dx  g x  {0,1}n Lagrangian Relaxation min cx s.t. x  Y Value integer program  Value Lagrangian relaxation Y + (b – Ax) For all :

Properties of the Lagrangian Relaxation: 

Properties of the Lagrangian Relaxation  z() is a piecewise affine concave function  To find the best lower bound, solve Lagrangian Dual max z() s.t.   m  To find a subgradient of z(), solve the Lagrangian relaxation

Nonsmooth Methods: 

Nonsmooth Methods  Kelley’s cutting plane  Subgradient optimisation (Held & Karp)  Projection methods (Conn & Cornuejols)  Method of analytic centres (Goffin et al.)  Box-step method (Marsten)  Bundle methods (Lemarechal, Kiwiel)  Linear-norm bundle methods (Kim et al.)  Penalty-step method (du Merle, Desrosiers et al.)  Partial-step method (Neame) = column generation!

A Common Framework: 

A Common Framework Iteratively solve max ( min { cx + (b – Ax) : x  Yi} ) s.t.   m + si() where Yi  Y Joint work with Danny Ralph & Phil Neame

Stabilisation Functions: 

Stabilisation Functions Box-step Bundle Bundle – 1-norm du Merle et al.

Better Theory and Algorithms: 

Better Theory and Algorithms  An algorithm for general stabilisation functions  General conditions on stabilisation functions under which the algorithm will - Converge - Terminate finitely  Termination of earlier methods: special cases These imply conditions on the parameters defining the stabilisation functions New (hybrid) stabilisation functions

Numerical Improvements: 

Numerical Improvements  Binary cutting stock problem  Average results over 20 problems drawn at random from 3 problem classes

Progress in Column Generation: 

Progress in Column Generation  Tailing off – slow convergence  Getting integrality – column generation within branch-and-bound and in combination with cutting planes*  Columns with set-up costs** * See Barnhart, Boland et al. 1998 & Boland et al. 2000 ** See Vanderbeck 2000  