1、Column GenerationJacques DesrosiersEcole des HEC&GERADCOLUMN GENERATION 2Contents The Cutting Stock Problem Basic Observations LP Column Generation Dantzig-Wolfe Decomposition Dantzig-Wolfe decomposition vs Lagrangian Relaxation Equivalenciesl Alternative Formulations to the Cutting Stock Probleml I
2、P Column Generationl Branch-and-.l Acceleration Techniquesl Concluding RemarksCOLUMN GENERATION 3A Classical Paper:The Cutting Stock ProblemP.C.Gilmore&R.E.GomoryA Linear Programming Approach to the Cutting Stock Problem.Oper.Res.9,849-859.(1960):set of items :number of times item i is requested :le
3、ngth of item i :length of a standard roll :set of cutting patterns :number of times item i is cut in pattern j :number of times pattern j is usedijailjYinIJLCOLUMN GENERATION 4The Cutting Stock Problem.Set can be huge.Solution of the linear relaxation of by column generation.JjYJjYIinYaYPjjJjijijJjj
4、,integer,0,min:JjYIinYaYLPjJjijijJjj,0,min:J,P,LPMinimize the number of standard rolls usedCOLUMN GENERATION 5The Cutting Stock Problem.Given a subsetand the dual multipliersthe reduced cost of any new patterns must satisfy:otherwise,is optimal.JjYIinYaYLPjJjijijJjj,0,min:JJ,),(IiJii;01minIiiijJJjaL
5、PCOLUMN GENERATION 6The Cutting Stock Problem.Reduced costs for are non negative,hence:is a decision variable:the number of times item i is selected in a new pattern.The Column Generatoris a Knapsack Problem.JjIiaLalaaaiIiiiIiiiIiijiJjIiijiJJjinteger,01min1min1min iaIiaLalaiIiiiIiiiinteger,0maxCOLUM
6、N GENERATION 7Basic ObservationsKeep the coupling constraints at a superior level,in a Master Problem;this with the goal of obtaining a Column Generator which is rather easy to solve.At an inferior level,solve the Column Generator,which is often separable in several independent sub-problems;use a sp
7、ecialized algorithm that exploits its particular structure.COLUMN GENERATION 8LP Column GenerationOptimality Conditions:primal feasibility complementary slackness dual feasibilityMASTER PROBLEMColumns Dual Multipliers COLUMN GENERATOR (Sub-problems)COLUMN GENERATION 9Historical PerspectiveG.B.Dantzi
8、g&P.WolfeDecomposition Principle for Linear Programs.Oper.Res.8,101-111.(1960)Authors give credit to:L.R.Ford&D.R.FulkersonA Suggested Computation for Multi-commodity flows.Man.Sc.5,97-101.(1958)COLUMN GENERATION 10Historical Perspective:a Dual ApproachJ.E.Kelly The Cutting Plane Method for Solving
9、Convex Programs.SIAM 8,703-712.(1960)DUAL MASTER PROBLEMRows Dual Multipliers ROW GENERATOR(Sub-problems)COLUMN GENERATION 11Dantzig-Wolfe Decomposition:the Principle)(,0)(,01:asrewritten )()(pp)()(rpdxxXConvxrprrrppp rays extreme:)(points extreme:)(sets define ),(On XconvXxbAxcxPmin:COLUMN GENERATI
10、ON 12Dantzig-Wolfe Decomposition:Substitution)(,0)(,01)()(min:)()()()()(rpbdxAdxcPrpppprrrppprrrppXxbAxcxPmin:COLUMN GENERATION 13)(,0)(,01)()()()(min:)()()()()(rpbAdAxcdcxPrpppprrrppprrrppDantzig-Wolfe Decomposition:The Master Problem)(,0)(,01)()(min:)()()()()(rpbdxAdxcPrpppprrrppprrrppThe Master P
11、roblemCOLUMN GENERATION 14Dantzig-Wolfe Decomposition:The Column GeneratorGiven the current dual multipliers for a subset of columns:coupling constraintsconvexity constraintgenerate (if possible)new columns with negative reduced cost:)()(min0XconvxAxcx)(,0)(if points extreme otherwise)(,0)(if rays e
12、xtreme0psomeforAxcxrsomefordAcppr)(oCOLUMN GENERATION 15)(,)(if points extreme otherwise)(,0)(if rays extreme0psomeforbbAxcxrsomefordAcpprRemark)(,0)(if points extreme otherwise)(,0)(if rays extreme0psomeforAxcxrsomefordAcpprCOLUMN GENERATION 16Dantzig-Wolfe Decomposition:Block Angular StructureExpl
13、oits the structure of many sub-problems.Similar developments&results.KkXxbxAxcPkkKkkkKkkk,min:COLUMN GENERATION 17Dantzig-Wolfe Decomposition:AlgorithmOptimality Conditions:primal feasibility complementary slackness dual feasibilityMASTER PROBLEMColumns Dual Multipliers COLUMN GENERATOR(Sub-problems
14、)COLUMN GENERATION 18Given the current dual multipliers (coupling constraints)(convexity constraint),a lower bound can be computed at each iteration,as follows:Dantzig-Wolfe Decomposition:a Lower BoundXxbAxcxXxAxcxb)(min)(min)(00)(oCurrent solution value+minimum reduced cost columnCOLUMN GENERATION
15、19).(max using obtained is boundlower best The.),()(;)(,0)(:on boundlower a provides)()(min)(LotherwisepsomeforbAxcxrsomefordAcifPXconvxbAxcxLpprLagrangian Relaxation Computes the Same Lower BoundXxbAxcxPmin:COLUMN GENERATION 20Dantzig-Wolfe vs Lagrangian Decomposition RelaxationEssentially utilized
16、for Linear ProgramsRelatively difficult to implement Slow convergenceRarely implementedEssentially utilizedfor Integer ProgramsEasy to implement with subgradient adjustment for multipliers No stopping rule!6%of OR papersCOLUMN GENERATION 21EquivalenciesDantzig-Wolfe Decomposition&Lagrangian Relaxati
17、onif both have the same sub-problemsIn both methods,coupling or complicating constraints go into a DUAL MULTIPLIERS ADJUSTMENT PROBLEM:in DW:a LP Master Problemin Lagrangian Relaxation:)(max LCOLUMN GENERATION 22Equivalencies.Column Generation corresponds to the solution process used in Dantzig-Wolf
18、e decomposition.This approach can also be used directly by formulating a Master Problem and sub-problems rather than obtaining them by decomposing a Global formulation of the problem.However.COLUMN GENERATION 23Equivalencies.for any Column Generation scheme,there exits a Global Formulationthat can b
19、e decomposed by using a generalized Dantzig-Wolfe decomposition which results in the same Master and sub-problems.The definition of the Global Formulationis not unique.A nice example:The Cutting Stock ProblemCOLUMN GENERATION 24.,integer,0,10,minKkIiXKkorYKkYLXlIinXYkikkIikiiiKkkiKkkThe Cutting Stoc
20、k Problem:Kantorovich(1960/1939):set of available rolls :binary variable,1 if roll k is cut,0 otherwise :number of times item i is cut on roll kKkYkiXCOLUMN GENERATION 25The Cutting Stock Problem:Kantorovich.Kantorovichs LP lower bound is weak:However,Dantzig-Wolfe decomposition provides the same bo
21、und as the Gilmore-Gomory LP bound if sub-problems are solved as.integer Knapsack Problems,(which provide extreme point columns).Aggregation of identical columns in the Master Problem.Branch&Bound performed on|K.kiX./LnlIiiiCOLUMN GENERATION 26The Cutting Stock Problem:Valerio de Carvalh(1996)Networ
22、k type formulation on graph),(AN1,.,1,0),1,(,0:),(,1,.,2,1,0LuuuIiluvandLvuvuALLNiExample with ,and 3,221ll5LCOLUMN GENERATION 27AvuXzXLvXXzXIinXZuvLuuLvuuvvuuvvviAluuluuii),(integer,0,1,2,1,0,min),(),(),(),0(0),(,The Cutting Stock Problem:Valerio de Carvalh.COLUMN GENERATION 28The Cutting Stock Pro
23、blem:Valerio de Carvalh.The sub-problem is ashortest path problem on a acyclic network.This Column Generator only brings back extreme ray columns,the single extreme point being the null vector.The Master Problem appears without the convexity constraint.The correspondence with Gilmore-Gomory formulat
24、ion is obvious.Branch&Bound performed on.uvXCOLUMN GENERATION 29The Cutting Stock Problem:Desaulniers et al.(1998)It can also be viewed as a Vehicle Routing Problem on a acyclic network(multi-commodity flows):Vehicles Rolls Customers Items Demands Capacity Column Generation tools developed for Routi
25、ng Problems can be used.Columns correspond to paths visiting items the requested number of times.Branch&Bound performed oniinl L.kijXCOLUMN GENERATION 30integer min:xXxbAxcxIPIP Column Generationinteger )(,0)(,01)()()()(min:)()()()()()()(xdxxrpbAdAxcdcxIPrrrppprpppprrrppprrrppCOLUMN GENERATION 31Int
26、egralityPropertyThe sub-problem satisfies the Integrality Property if it has an integer optimal solution for any choice of linear objective function,even if the integrality restrictions on the variables are relaxed.In this case,otherwisei.e.,the solution process partially explores the integrality ga
27、p.)()(maxLPvL)()(max)(IPvLLPvCOLUMN GENERATION 32IntegralityProperty.In most cases,the Integrality Property is a undesirable property!Exploiting the non trivial integer structure reveals that.some overlooked formulations become very good when a Dantzig-Wolfe decomposition process is applied to them.
28、The Cutting Stock ProblemLocalization ProblemsVehicle Routing Problems.COLUMN GENERATION 33IP Column Generation:Branch-and-.Branch-and-Bound:branching decisions on a combination of the original(fractional)variablesof a Global Formulation on which Dantzig-Wolfe Decomposition is applied.Branch-and-Cut
29、:cutting planes defined on a combination of the original variables;l at the Master level,as coupling constraints;l in the sub-problem,as local constraints.COLUMN GENERATION 34IP Column Generation:Branch-and-.Branching&Cutting decisionsinteger min:xXxbAxxcIPDantzig-Wolfe decomposition applied at all
30、decision nodesCOLUMN GENERATION 35IP Column Generation:Branch-and-.Branch-and-Price:a nice name which hides a well known solution process relatively easy to apply.For alternative methods,see the work ofS.Holm&J.TindC.Barnhart,E.Johnson,G.Nemhauser,P.Vance,M.Savelsbergh,.F.Vanderbeck&L.WolseyCOLUMN G
31、ENERATION 36Application to Vehicle Routing and Crew Scheduling Problems(1981-)Global Formulation:Non-Linear Integer Multi-Commodity FlowsMaster Problem:Covering&Other Linking ConstraintsColumn Generator:Resource Constrained Shortest Pathsl J.Desrosiers,Y.Dumas,F.Soumis&M.SolomonTime Constrained Rout
32、ing and SchedulingHandbooks in OR&MS,8 (1995)l G.Desaulniers et al.A Unified Framework for Deterministic Vehicle Routing and Crew Scheduling Problems T.Crainic&G.Laporte(eds)Fleet Management&Logistics(1998)COLUMN GENERATION 37Resource Constrained Shortest Path Problem on G=(N,A)NiRrriiAjiijijTxcMin)
33、,(doidioixxAijjijAjijij,0;,1;,1),(:),(:RrAjiTTfxrjiijij,),(,0)(AjixRrNibxTaxijriAjijijririAjijij),(,binary,)()(),(:),(:P(N,A):COLUMN GENERATION 38Integer Multi-Commodity Network Flow StructureKkNiRrkrikiAjikijkijkkTxcMin)(),(MmbTaxaNibxmKkkriNikrimAjikijkijmKkkiKkAjijkijkkk,)(,)(,),(,),(:KkANPTxkkkk
34、 ),(),(COLUMN GENERATION 39Vehicle Routing and Crew Scheduling Problems.Sub-Problem is strongly NP-hardIt does not posses the Integrality PropertyPaths Extreme pointsMaster Problem results in Set Partitioning/Covering type ProblemsBranching and Cutting decisions are taken on the original network flo
35、w,resource and supplementary variablesCOLUMN GENERATION 40IP Column Generation:Acceleration Techniqueson the Column Generator Master Problem Global FormulationWith Fast Heuristics Re-Optimizers Pre-ProcessorsTo get Primal&Dual SolutionsExploit all the StructuresCOLUMN GENERATION 41IP Column Generati
36、on:Acceleration Techniques.Multiple Columns:selected subset close to expected optimal solutionPartial Pricing in case of many Sub-Problems:as in the Simplex MethodEarly&Multiple Branching&Cutting :quickly gets local optimaPrimal Perturbation&Dual Restriction:to avoid degeneracy and convergence diffi
37、cultiesBranching&Cutting:on integer variables!Branch-first,Cut-second Approach:exploit solution structuresLink all the StructuresBe Innovative!COLUMN GENERATION 42Stabilized Column Generation0minxbAxcxcAbmax21maxddcAbRestricted Dual2211210,00minyyxbyyAxcxPerturbed Primal 22112122110,00minyyxbyyAxydy
38、dcxStabilized Problem COLUMN GENERATION 43Concluding Remarksl DW Decomposition is an intuitive framework that requires all tools discussed to become applicablel “easier”for IP l very effective in several applicationsImagine what could be done with theoretically better methods such as the Analytic Ce
39、nter Cutting Plane Method(Vial,Goffin,du Merle,Gondzio,Haurie,et al.)which exploits recent developments in interior point methods,and is also compatible with Column Generation.COLUMN GENERATION 44“Bridging Continents and Cultures”F.SoumisM.Solomon G.DesaulniersP.HansenJ.-L.GoffinO.MarcotteG.SavardO.
40、du MerleO.MadsenP.O.LindbergB.JaumardM.DesrochersY.DumasM.GamacheD.VilleneuveK.ZiaratiI.IoachimM.StojkovicG.StojkovicN.KohlA.Nu et al.Canada,USA,Italy,Denmark,Sweden,Norway,Ile Maurice,France,Iran,Congo,New Zealand,Brazil,Australia,Germany,Romania,Switzerland,Belgium,Tunisia,Mauritania,Portugal,China,The Netherlands,.
