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

ColumnGeneration,JacquesDesrosiersEcoledesHECthiswiththegoalofobtainingaColumnGeneratorwhichisrathereasytosolve.,Ataninferiorlevel,solvetheColumnGenerator,whichisoftenseparableinseveralindependentsub-problems;useaspecializedalgorithmthatexploitsitsparticularstructure.,-,COLUMNGENERATION8,LPColumnGeneration,OptimalityConditions:primalfeasibilitycomplementaryslacknessdualfeasibility,MASTERPROBLEMColumnsDualMultipliersCOLUMNGENERATOR(Sub-problems),-,COLUMNGENERATION9,HistoricalPerspective,G.B.DantzigattheMasterlevel,ascouplingconstraints;inthesub-problem,aslocalconstraints.,-,COLUMNGENERATION34,IPColumnGeneration:Branch-and-.,Branching&Cuttingdecisions,Dantzig-Wolfedecompositionappliedatalldecisionnodes,-,COLUMNGENERATION35,IPColumnGeneration:Branch-and-.,Branch-and-Price:anicenamewhichhidesawellknownsolutionprocessrelativelyeasytoapply.,Foralternativemethods,seetheworkofS.Holm&J.TindC.Barnhart,E.Johnson,G.Nemhauser,P.Vance,M.Savelsbergh,.F.Vanderbeck&L.Wolsey,-,COLUMNGENERATION36,ApplicationtoVehicleRoutingandCrewSchedulingProblems(1981-),GlobalFormulation:Non-LinearIntegerMulti-CommodityFlowsMasterProblem:Covering&OtherLinkingConstraintsColumnGenerator:ResourceConstrainedShortestPaths,J.Desrosiers,Y.Dumas,F.Soumis&M.SolomonTimeConstrainedRoutingandSchedulingHandbooksinOR&MS,8(1995)G.Desaulniersetal.AUnifiedFrameworkforDeterministicVehicleRoutingandCrewSchedulingProblemsT.Crainic&G.Laporte(eds)FleetManagement&Logistics(1998),-,COLUMNGENERATION37,ResourceConstrainedShortestPathProblemonG=(N,A),P(N,A):,-,COLUMNGENERATION38,IntegerMulti-CommodityNetworkFlowStructure,-,COLUMNGENERATION39,VehicleRoutingandCrewSchedulingProblems.,Sub-ProblemisstronglyNP-hardItdoesnotpossestheIntegralityPropertyPathsExtremepoints,MasterProblemresultsinSetPartitioning/CoveringtypeProblems,BranchingandCuttingdecisionsaretakenontheoriginalnetworkflow,resourceandsupplementaryvariables,-,COLUMNGENERATION40,IPColumnGeneration:AccelerationTechniques,ontheColumnGeneratorMasterProblemGlobalFormulation,WithFastHeuristicsRe-OptimizersPre-Processors,TogetPrimal&DualSolutions,ExploitalltheStructures,-,COLUMNGENERATION41,IPColumnGeneration:AccelerationTechniques.,MultipleColumns:selectedsubsetclosetoexpectedoptimalsolutionPartialPricingincaseofmanySub-Problems:asintheSimplexMethodEarly&MultipleBranching&Cutting:quicklygetslocaloptima,PrimalPerturbation&DualRestriction:toavoiddegeneracyandconvergencedifficultiesBranching&Cutting:onintegervariables!Branch-first,Cut-secondApproach:exploitsolutionstructures,LinkalltheStructures,BeInnovative!,-,COLUMNGENERATION42,StabilizedColumnGeneration,RestrictedDual,PerturbedPrimal,StabilizedProblem,-,COLUMNGENERATION43,ConcludingRemarks,DWDecompositionisanintuitiveframeworkthatrequiresalltoolsdiscussedtobecomeapplicable“easier”forIPveryeffectiveinseveralapplicationsImaginewhatcouldbedonewiththeoreticallybettermethodssuchas,theAnalyticCenterCuttingPlaneMethod(Vial,Goffin,duMerle,Gondzio,Haurie,etal.)whichexploitsrecentdevelopmentsininteriorpointmethods,andisalsocompatiblewithColumnGeneration.,-,COLUMNGENERATION44,“BridgingContinentsandCultures”,F.SoumisM.SolomonG.DesaulniersP.HansenJ.-L.GoffinO.MarcotteG.SavardO.duMerleO.MadsenP.O.LindbergB.Jaumard,M.DesrochersY.DumasM.GamacheD.VilleneuveK.ZiaratiI.IoachimM.StojkovicG.StojkovicN.KohlA.Nuetal.,Canada,US