[数学]列生成算法介绍ppt课件

1、Column GenerationJacques DesrosiersEcole des HEC & GERADContents 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 Genera

2、tion Branch-and- . Acceleration Techniques Concluding RemarksA 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 : length of item i : le

3、ngth of a standard roll : set of cutting patterns : number of times item i is cut in pattern j : number of times pattern j is usedijailjYinIJLThe Cutting Stock Problem .Set can be huge.Solution of the linear relaxation of by column generation.JjYJjYIinYaYPjjJjijijJjj,integer,0,min:JjYIinYaYLPjJjijij

4、Jjj,0,min:J, P,LPMinimize the number of standard rolls usedThe 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;01minIiiijJJjaLPThe Cutting Stock Problem .Reduced costs for a

5、re 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, 0maxBasic ObservationsKeep the coupling constraints at a superior le

6、vel, 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.LP Column Genera

7、tionOptimality Conditions: primal feasibility complementary slackness dual feasibilityMASTER PROBLEMColumns Dual Multipliers COLUMN GENERATOR (Sub-problems)Historical PerspectiveG.B. Dantzig & P. WolfeDecomposition Principle for Linear Programs. Oper. Res. 8, 101-111. (1960)Authors give credit t

8、o:L.R. Ford & D.R. FulkersonA Suggested Computation for Multi-commodity flows.Man. Sc. 5, 97-101. (1958)Historical Perspective : a Dual ApproachJ.E. Kelly The Cutting Plane Method for Solving Convex Programs. SIAM 8, 703-712. (1960) DUAL MASTER PROBLEMRows Dual Multipliers ROW GENERATOR(Sub-prob

9、lems)Dantzig-Wolfe Decomposition :the Principle)(, 0)(, 01:asrewritten )()(pp)()(rpdxxXConvxrprrrppp rays extreme: )( points extreme : )(sets define ),(On XconvXxbAxcxPmin:Dantzig-Wolfe Decomposition : Substitution)(, 0)(, 01)()(min:)()()()()(rpbdxAdxcPrpppprrrppprrrppXxbAxcxPmin:)(, 0)(, 01)()()()(

10、min:)()()()()(rpbAdAxcdcxPrpppprrrppprrrppDantzig-Wolfe Decomposition : The Master Problem)(, 0)(, 01)()(min:)()()()()(rpbdxAdxcPrpppprrrppprrrppThe Master ProblemDantzig-Wolfe Decomposition : The Column GeneratorGiven the current dual multipliers for a subset of columns :coupling constraintsconvexi

11、ty constraintgenerate (if possible)new columns with negative reduced cost :)()(min0XconvxAxcx)(,0)( if points extreme otherwise)(,0)(if rays extreme0psomeforAxcxrsomefordAcppr)(o)(,)( if points extreme otherwise)(,0)(if rays extreme0psomeforbbAxcxrsomefordAcpprRemark )(,0)( if points extreme otherwi

12、se)(,0)(if rays extreme0psomeforAxcxrsomefordAcpprDantzig-Wolfe Decomposition : Block Angular StructureExploits the structure of many sub-problems.Similar developments& results.KkXxbxAxcPkkKkkkKkkk,min:Dantzig-Wolfe Decomposition : AlgorithmOptimality Conditions: primal feasibility complementary

13、 slackness dual feasibilityMASTER PROBLEMColumns Dual Multipliers COLUMN GENERATOR(Sub-problems)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 BoundXxbAxcxXxAxcxb)(min)(

14、min)(00)(oCurrent solution value + minimum reduced cost column).(max using obtained is boundlower best The.),()(; )(, 0)(:on boundlower a provides)()(min)(LotherwisepsomeforbAxcxrsomefordAcifPXconvxbAxcxLpprLagrangian Relaxation Computes the Same Lower BoundXxbAxcxPmin:Dantzig-Wolfe vs Lagrangian De

15、composition RelaxationEssentially utilizedfor Linear ProgramsRelatively difficult to implement Slow convergenceRarely implementedEssentially utilizedfor Integer ProgramsEasy to implement with subgradient adjustment for multipliers No stopping rule ! 6% of OR papersEquivalenciesDantzig-Wolfe Decompos

16、ition &Lagrangian Relaxationif 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 LEquivalencies .Column Generation corresponds to the solution process used

17、 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 .Equivalencies . for any Column Generation scheme, there exits a Global Formulation that ca

18、n be 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 Problem. ,integer,0, 10,minKkIiXKkorYKkYLXlIinXYkikkIikiiiKkkiKkkThe Cutting Stock Problem : Kan

19、torovich (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 kKkYkiXThe Cutting Stock Problem : Kantorovich . Kantorovichs LP lower bound is weak:However, Dantzig-Wolfe decomposition provides the same bound as the Gilmore-Go

20、mory 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./ LnlIiiiThe Cutting Stock Problem : Valerio de Carvalh (1996)Network type formulation on g

21、raph),(AN1,.,1 , 0),1,(,0: ),(, 1,.,2, 1, 0LuuuIiluvandLvuvuALLNiExample with , and 3, 221ll5LAvuXzXLvXXzXIinXZuvLuuLvuuvvuuvvviAluuluuii),( integer, 0,1,2, 1,0,min),(),(),(),0(0),(,The Cutting Stock Problem : Valerio de Carvalh . The Cutting Stock Problem : Valerio de Carvalh .The sub-problem is as

22、hortest 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 o

23、n.uvXThe 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 vis

24、iting items the requested number of times.Branch & Bound performed oniinl L.kijXinteger min:xXxbAxcxIPIP Column Generationinteger )(, 0)(, 01)()()()(min:)()()()()()()(xdxxrpbAdAxcdcxIPrrrppprpppprrrppprrrppIntegralityPropertyThe sub-problem satisfies the Integrality Property if it has an integer

25、 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 gap.)()(maxLPvL)()(max)(IPvLLPvIntegralityProperty .In most cases, the Integrality Pro

26、perty 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.IP Column Generation :Branch

27、-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 : cutting planes defined on a combination of the original variables; at the Master level, as coupling constraints

28、; in the sub-problem, as local constraints.IP Column Generation :Branch-and-. Branching & Cutting decisionsinteger min:xXxbAxxcIPDantzig-Wolfe decomposition applied at all decision nodesIP Column Generation:Branch-and-.Branch-and-Price :a nice name which hides a well known solution process relat

29、ively 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. WolseyApplication to Vehicle Routing and Crew Scheduling Problems (1981 - )Global Formulation :Non-Linear Integer Multi-Commodity

30、 FlowsMaster Problem : Covering & Other Linking ConstraintsColumn Generator : Resource Constrained Shortest Pathsl J. Desrosiers, Y. Dumas, F. Soumis & M. SolomonTime Constrained Routing and SchedulingHandbooks in OR & MS, 8 (1995)l G. Desaulniers et al. A Unified Framework for Determini

31、stic Vehicle Routing and Crew Scheduling Problems T. Crainic & G. Laporte (eds) Fleet Management & Logistics (1998)Resource Constrained Shortest Path Problem on G=(N,A)NiRrriiAjiijijTxcMin),(doidioixxAijjijAjijij, 0;, 1;, 1),( :),( :RrAjiTTfxrjiijij,),(, 0)(AjixRrNibxTaxijriAjijijririAjijij)

32、,(,binary ,)()(),( :),( :P(N, A) :Integer Multi-Commodity Network Flow StructureKkNiRrkrikiAjikijkijkkTxcMin)(),(MmbTaxaNibxmKkkriNikrimAjikijkijmKkkiKkAjijkijkkk,)(,)(,),(,),( :KkANPTxkkkk ),(),(Vehicle Routing and Crew Scheduling Problems .Sub-Problem is strongly NP-hardIt does not posses the Inte

33、grality PropertyPaths Extreme pointsMaster Problem results in Set Partitioning/Covering type ProblemsBranching and Cutting decisions are taken on the original network flow, resource and supplementary variablesIP Column Generation :Acceleration Techniqueson the Column Generator Master Problem Global

34、FormulationWith Fast Heuristics Re-Optimizers Pre-ProcessorsTo get Primal & Dual SolutionsExploit all the StructuresIP Column Generation :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 difficultiesBranching & Cutting : on integer variables !Branch-fi