列生成算法介绍.ppt

du titre du masque,Cliquez pour modifier les styles du texte du masque,Deuxime niveau,Troisime niveau,Quatrime niveau,Cinquime niveau,*,*,COLUMN GENERATION,*,Column Generation,Jacques,Desrosiers,Ecole des HEC,&,GERAD,Contents,The Cutting Stock Problem,Basic Observations,LP Column Generation,Dantzig-Wolfe Decomposition,Dantzig-Wolfe decomposition,vs,Lagrangian Relaxation,Equivalencies,Alternative Formulations to the Cutting Stock Problem,IP Column Generation,Branch-and-.,Acceleration Techniques,Concluding Remarks,2,A Classical Paper:The Cutting Stock Problem,P.C.Gilmore&R.E.Gomory,A Linear Programming Approach to the Cutting Stock Problem.,Oper.Res.9,849-859.,(1960),:,set of,items,:,number of times,item,i,is requested,:,length 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 used,3,The Cutting Stock Problem.,Set,can be huge.,Solution of the linear relaxation of by column generation.,Minimize the number of standard rolls used,4,The Cutting Stock Problem.,Given a subset,and the dual multipliers,the reduced cost of any new patterns must satisfy:,otherwise,is optimal.,5,The 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,.,6,Basic Observations,Keep 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 specialized algorithm that exploits its particular structure.,7,LP Column Generation,Optimality Conditions,:,primal feasibility,complementary slackness,dual feasibility,MASTER PROBLEM,Columns,Dual Multipliers,COLUMN GENERATOR (Sub-problems),8,Historical Perspective,G.B.Dantzig&P.Wolfe,Decomposition Principle for Linear Programs.,Oper.Res.8,101-111.(1960),Authors give credit to:,L.R.Ford&D.R.Fulkerson,A Suggested Computation for Multi-commodity flows.,Man.Sc.5,97-101.(1958),9,Historical Perspective:a Dual Approach,J.E.Kelly,The Cutting Plane Method for Solving Convex Programs.,SIAM 8,703-712.,(1960),DUAL MASTER PROBLEM,Rows,Dual Multipliers,ROW GENERATOR(Sub-problems),10,Dantzig-Wolfe Decomposition:the Principle,11,Dantzig-Wolfe Decomposition:Substitution,12,Dantzig-Wolfe Decomposition:The Master Problem,The Master Problem,13,Dantzig-Wolfe Decomposition:The Column Generator,Given the current dual multipliers for a subset of columns:,coupling,constraints,convexity,constraint,generate (,if possible,)new columns with negative reduced cost:,14,Remark,15,Dantzig-Wolfe Decomposition:Block Angular Structure,Exploits the structure of many sub-problems.,Similar developments&results.,16,Dantzig-Wolfe Decomposition:Algorithm,Optimality Conditions,:,primal feasibility,complementary slackness,dual,feasibility,MASTER PROBLEM,Columns,Dual Multipliers,COLUMN GENERATOR(Sub-problems),17,Given the current dual multipliers,(,coupling,constraints)(,convexity,constraint),a,lower bound,can be computed at each iteration,as follows:,Dantzig-Wolfe Decomposition:a Lower Bound,Current solution value,+,minimum,reduced cost column,18,Lagrangian Relaxation Computes the Same Lower Bound,19,Dantzig-Wolfe,vs,Lagrangian Decomposition Relaxation,Essentially utilizedfor Linear Programs,Relatively difficult to implement,Slow convergence,Rarely implemented,Essentially utilizedfor Integer Programs,Easy to implement with subgradient adjustment for multipliers,No stopping rule!,6%of OR papers,20,Equivalencies,Dantzig-Wolfe Decomposition&,Lagrangian Relaxation,if both have the same sub-problems,In both methods,coupling or complicating constraints go into a,DUAL MULTIPLIERS ADJUSTMENT PROBLEM,:,in DW:,a LP Master Problem,in Lagrangian Relaxation:,21,Equivalencies.,Column Generation,corresponds to the solution process used in,Dantzig-Wolfe,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.,22,Equivalencies.,for any,Column Generation scheme,there exits a,Global Formulation,that can be decomposed by using a,generalized Dantzig-Wolfe decomposition,which results in the same,Master and sub-problems,.,The definition of the,Global Formulation,is,not unique,.,A nice example:,The Cutting Stock Problem,23,The Cutting Stock 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,k,24,The Cutting Stock Problem:Kantorovich.,Kantorovichs LP lower bound is weak:,However,Dantzig-Wolfe decomposition provides the same bound 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,25,The Cutting Stock Problem:Valerio de Carvalh,(1996),Network type formulation on graph,Example with ,and,26,The Cutting Stock Problem:Valerio de Carvalh,.,27,The Cutting Stock Problem: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 formulation is obvious.,Branch&Bound performed on,28,The 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 Routing Problems can be used.,Columns correspond to paths visiting items the requested number of times,.,Branch&Bound performed on,29,IP Column Generation,30,IntegralityProperty,The 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,otherwise,i.e.,the solution process partially explores the integrality gap.,31,IntegralityProperty.,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.,The Cutting Stock ProblemLocalization ProblemsVehicle Routing Problems.,32,IP Column Generation:Branch-and-.,Branch-and-Bound:,branching decisions on a combination of the original,(,fractional,),variables,of a,Global Formulation,on which Dantzig-Wolfe Decomposition is applied.,Branch-and-Cut:,cutting planes defined on a combination of the original variables;,at the,Master,level,as coupling constraints;,in the,sub-problem,as local constraints.,33,IP Column Generation:Branch-and-.,Branching&,Cutting decisions,Dantzig-Wolfe decomposition applied at all decision nodes,34,IP 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 of,S.Holm&J.Tind,C.Barnhart,E.Johnson,G.Nemhauser,P.Vance,M.Savelsbergh,.,F.Vanderbeck&L.Wolsey,35,Application to,Vehicle Routing,and,Crew Scheduling Problems,(1981-),Global Formulation,:Non-Linear Integer Multi-Commodity Flows,Master Problem,:Covering&Other Linking Constraints,Column Generator,:Resource Constrained Shortest Paths,J.Desrosiers,Y.Dumas,F.Soumis&M.Solomon,Time Constrained Routing and Scheduling,Handbooks in OR&MS,8,(1995),G.Desaulniers,et al.,A Unified Framework for Deterministic Vehicle Routing and Crew Scheduling Problems,T.,Crainic,&G.,Laporte,(,eds,),Fleet Management&Logistics,(1998),36,Resource Constrained Shortest Path Problem on G=(N,A),P,(,N,A,):,37,Integer Multi-Commodity Network Flow Structure,38,Vehicle Routing and Crew Scheduling Problems.,Sub-Problem,is,strongly NP-hard,It does not posses the,Integrality Property,Paths,Extreme points,Master Problem,results in,Set Partitioning/Covering,type Problems,Branching and Cutting decisions are taken on the,original network flow,resource and supplementary variables,39,IP Column Generation:Acceleration Techniques,on the,Column Generator,Master Problem,Global Formulation,With Fast,Heuristics,Re-Optimizers,Pre-Processors,To get,Primal,&,Dual,Solutions,Exploit all the Structures,40,IP Column Generation:Acceleration Techniques.,Multiple Columns,:selected subset close to expected optimal solution,Partial Pricing in case of many Sub-Problems,:,as in the Simplex Method,Early&Multiple Branching&Cutting,:quickly gets local optima,Primal Perturbation&Dual Restriction,:,to avoid degeneracy and convergence difficulties,Branching&Cutting,:on,integer,variables!,Branch-first,Cut-second Approach,:,exploit solution structures,Link all the Structures,Be Innovative!,41,Stabilized Column Generation,Restricted,Dual,Perturbed,Primal,Stabilized,Problem,42,Concluding Remarks,DW Decomposition,is an intuitive framework that requires all tools discussed to become applicable,“easier”for IP,very effective in several applications,Imagine what could be done with theoretically better methods such as,the,Analytic Center 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.,43,“Bridging Continents and Cultures”,F.Soumis,M.Solomon,G.Desaulniers,P.Hansen,J.-L.Goffin,O.Marcotte,G.Savard,O.du Merle,O.Madsen,P.O.Lindberg,B.Jaumard,M.Desrochers,Y.Dumas,M.Gamache,D.Villeneuve,K.Ziarati,I.Ioachim,M.Stojkovic,G.Stojkovic,N.Kohl,A.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,.,44,