列生成算法介绍PPT文档格式.ppt
《列生成算法介绍PPT文档格式.ppt》由会员分享,可在线阅读,更多相关《列生成算法介绍PPT文档格式.ppt(44页珍藏版)》请在冰点文库上搜索。
![列生成算法介绍PPT文档格式.ppt](https://file1.bingdoc.com/fileroot1/2023-4/28/1ce94c89-b50e-42b5-8a0b-73a53527832c/1ce94c89-b50e-42b5-8a0b-73a53527832c1.gif)
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&
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