列生成算法介绍.ppt

列生成算法介绍.ppt

《列生成算法介绍.ppt》由会员分享，可在线阅读，更多相关《列生成算法介绍.ppt（44页珍藏版）》请在冰点文库上搜索。

ColumnGeneration,JacquesDesrosiersEcoledesHEC&GERAD,COLUMNGENERATION2,Contents,TheCuttingStockProblemBasicObservationsLPColumnGenerationDantzig-WolfeDecompositionDantzig-WolfedecompositionvsLagrangianRelaxationEquivalencies,AlternativeFormulationstotheCuttingStockProblemIPColumnGenerationBranch-and-.AccelerationTechniquesConcludingRemarks,COLUMNGENERATION3,AClassicalPaper:

TheCuttingStockProblem,P.C.Gilmore&R.E.GomoryALinearProgrammingApproachtotheCuttingStockProblem.Oper.Res.9,849-859.（1960）,:

setofitems:

numberoftimesitemiisrequested:

lengthofitemi:

lengthofastandardroll:

setofcuttingpatterns:

numberoftimesitemiiscutinpatternj:

numberoftimespatternjisused,COLUMNGENERATION4,TheCuttingStockProblem.,Setcanbehuge.Solutionofthelinearrelaxationofbycolumngeneration.,Minimizethenumberofstandardrollsused,COLUMNGENERATION5,TheCuttingStockProblem.,Givenasubsetandthedualmultipliersthereducedcostofanynewpatternsmustsatisfy:

otherwise,isoptimal.,COLUMNGENERATION6,TheCuttingStockProblem.,Reducedcostsforarenonnegative,hence:

isadecisionvariable:

thenumberoftimesitemiisselectedinanewpattern.TheColumnGeneratorisaKnapsackProblem.,COLUMNGENERATION7,BasicObservations,Keepthecouplingconstraintsatasuperiorlevel,inaMasterProblem;thiswiththegoalofobtainingaColumnGeneratorwhichisrathereasytosolve.,Ataninferiorlevel,solvetheColumnGenerator,whichisoftenseparableinseveralindependentsub-problems;useaspecializedalgorithmthatexploitsitsparticularstructure.,COLUMNGENERATION8,LPColumnGeneration,OptimalityConditions:

primalfeasibilitycomplementaryslacknessdualfeasibility,MASTERPROBLEMColumnsDualMultipliersCOLUMNGENERATOR（Sub-problems）,COLUMNGENERATION9,HistoricalPerspective,G.B.Dantzig&P.WolfeDecompositionPrincipleforLinearPrograms.Oper.Res.8,101-111.（1960）,Authorsgivecreditto:

L.R.Ford&D.R.FulkersonASuggestedComputationforMulti-commodityflows.Man.Sc.5,97-101.（1958）,COLUMNGENERATION10,HistoricalPerspective:

aDualApproach,J.E.KellyTheCuttingPlaneMethodforSolvingConvexPrograms.SIAM8,703-712.（1960）,DUALMASTERPROBLEMRowsDualMultipliersROWGENERATOR（Sub-problems）,COLUMNGENERATION11,Dantzig-WolfeDecomposition:

thePrinciple,COLUMNGENERATION12,Dantzig-WolfeDecomposition:

Substitution,COLUMNGENERATION13,Dantzig-WolfeDecomposition:

TheMasterProblem,TheMasterProblem,COLUMNGENERATION14,Dantzig-WolfeDecomposition:

TheColumnGenerator,Giventhecurrentdualmultipliersforasubsetofcolumns:

couplingconstraintsconvexityconstraintgenerate（ifpossible）newcolumnswithnegativereducedcost:

COLUMNGENERATION15,Remark,COLUMNGENERATION16,Dantzig-WolfeDecomposition:

BlockAngularStructure,Exploitsthestructureofmanysub-problems.Similardevelopments&results.,COLUMNGENERATION17,Dantzig-WolfeDecomposition:

Algorithm,OptimalityConditions:

primalfeasibilitycomplementaryslacknessdualfeasibility,MASTERPROBLEMColumnsDualMultipliersCOLUMNGENERATOR（Sub-problems）,COLUMNGENERATION18,Giventhecurrentdualmultipliers（couplingconstraints）（convexityconstraint）,alowerboundcanbecomputedateachiteration,asfollows:

Dantzig-WolfeDecomposition:

aLowerBound,Currentsolutionvalue+minimumreducedcostcolumn,COLUMNGENERATION19,LagrangianRelaxationComputestheSameLowerBound,COLUMNGENERATION20,Dantzig-WolfevsLagrangianDecompositionRelaxation,EssentiallyutilizedforLinearProgramsRelativelydifficulttoimplementSlowconvergenceRarelyimplemented,EssentiallyutilizedforIntegerProgramsEasytoimplementwithsubgradientadjustmentformultipliersNostoppingrule!

6%ofORpapers,COLUMNGENERATION21,Equivalencies,Dantzig-WolfeDecomposition&LagrangianRelaxationifbothhavethesamesub-problems,Inbothmethods,couplingorcomplicatingconstraintsgointoaDUALMULTIPLIERSADJUSTMENTPROBLEM:

inDW:

aLPMasterProbleminLagrangianRelaxation:

COLUMNGENERATION22,Equivalencies.,ColumnGenerationcorrespondstothesolutionprocessusedinDantzig-Wolfedecomposition.ThisapproachcanalsobeuseddirectlybyformulatingaMasterProblemandsub-problemsratherthanobtainingthembydecomposingaGlobalformulationoftheproblem.However.,COLUMNGENERATION23,Equivalencies.,foranyColumnGenerationscheme,thereexitsaGlobalFormulationthatcanbedecomposedbyusingageneralizedDantzig-WolfedecompositionwhichresultsinthesameMasterandsub-problems.,ThedefinitionoftheGlobalFormulationisnotunique.Aniceexample:

TheCuttingStockProblem,COLUMNGENERATION24,TheCuttingStockProblem:

Kantorovich（1960/1939）,:

setofavailablerolls:

binaryvariable,1ifrollkiscut,0otherwise:

numberoftimesitemiiscutonrollk,COLUMNGENERATION25,TheCuttingStockProblem:

Kantorovich.,KantorovichsLPlowerboundisweak:

However,Dantzig-WolfedecompositionprovidesthesameboundastheGilmore-GomoryLPboundifsub-problemsaresolvedas.,integerKnapsackProblems,（whichprovideextremepointcolumns）.AggregationofidenticalcolumnsintheMasterProblem.Branch&Boundperformedon,COLUMNGENERATION26,TheCuttingStockProblem:

ValeriodeCarvalh（1996）,Networktypeformulationongraph,Examplewith,and,COLUMNGENERATION27,TheCuttingStockProblem:

ValeriodeCarvalh.,COLUMNGENERATION28,TheCuttingStockProblem:

ValeriodeCarvalh.,Thesub-problemisashortestpathproblemonaacyclicnetwork.ThisColumnGeneratoronlybringsbackextremeraycolumns,thesingleextremepointbeingthenullvector.,TheMasterProblemappearswithouttheconvexityconstraint.ThecorrespondencewithGilmore-Gomoryformulationisobvious.Branch&Boundperformedon,COLUMNGENERATION29,TheCuttingStockProblem:

Desaulniersetal.（1998）,ItcanalsobeviewedasaVehicleRoutingProblemonaacyclicnetwork（multi-commodityflows）:

VehiclesRollsCustomersItemsDemandsCapacity,ColumnGenerationtoolsdevelopedforRoutingProblemscanbeused.Columnscorrespondtopathsvisitingitemstherequestednumberoftimes.Branch&Boundperformedon,COLUMNGENERATION30,IPColumnGeneration,COLUMNGENERATION31,IntegralityProperty,Thesub-problemsatisfiestheIntegralityPropertyifithasanintegeroptimalsolutionforanychoiceoflinearobjectivefunction,eveniftheintegralityrestrictionsonthevariablesarerelaxed.,Inthiscase,otherwisei.e.,thesolutionprocesspartiallyexplorestheintegralitygap.,COLUMNGENERATION32,IntegralityProperty.,Inmostcases,theIntegralityPropertyisaundesirableproperty!

Exploitingthenontrivialintegerstructurerevealsthat.,someoverlookedformulationsbecomeverygoodwhenaDantzig-Wolfedecompositionprocessisappliedtothem.TheCuttingStockProblemLocalizationProblemsVehicleRoutingProblems.,COLUMNGENERATION33,IPColumnGeneration:

Branch-and-.,Branch-and-Bound:

branchingdecisionsonacombinationoftheoriginal（fractional）variablesofaGlobalFormulationonwhichDantzig-WolfeDecompositionisapplied.,Branch-and-Cut:

cuttingplanesdefinedonacombinationoftheoriginalvariables;attheMasterlevel,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,“BridgingContinentsand