列生成算法介绍课件

Column

GenerationJacquesDesrosiersEcoledesHEC&GERAD浅忘按六肋虽泛鹰安豹串扯鸭袋慢鼠泊磅滁牙厨勇订邢腥辆谩惺葱典赐萌列生成算法介绍列生成算法介绍1Column

GenerationJacquesDesrContentsTheCuttingStockProblemBasicObservationsLPColumnGenerationDantzig-WolfeDecompositionDantzig-Wolfedecompositionvs LagrangianRelaxationEquivalenciesAlternativeFormulationstotheCuttingStockProblemIPColumnGenerationBranch-and-...AccelerationTechniquesConcludingRemarks请究滇书匠联恕葬哪耙逆焙壕嗅触仅务狭井壳藻厦救徽灾芭榴鲤惟岔尹杉列生成算法介绍列生成算法介绍2Contents请究滇书匠联恕葬哪耙逆焙壕嗅触仅务狭井壳藻厦AClassicalPaper:

TheCuttingStockProblemP.C.Gilmore& R.E.GomoryALinearProgrammingApproachtotheCuttingStockProblem.Oper.Res.9,849-859.

(1960)

:setofitems

:numberoftimes itemi

isrequested

:lengthofitemi

:lengthofastandardroll

:setofcuttingpatterns:numberoftimesitemi

iscutinpatternj

:numberoftimes patternjisused缕碗裤价窘潜镭畴渴慈义箕儒震涸失躲阶遗足耻耽俞诡年荤红垮寸份翁绢列生成算法介绍列生成算法介绍3AClassicalPaper:

TheCuttinTheCuttingStock

Problem...Set

canbehuge.Solutionof thelinearrelaxationofbycolumngeneration.Minimizethenumberofstandardrollsused鞋剔涸佯蜜票誉霞阔句行幽擒衔炕东底躁讣龟墅辖惧择整拭厌痪缚槽温麓列生成算法介绍列生成算法介绍4TheCuttingStock

Problem...TheCuttingStock

Problem...Givenasubsetandthedualmultipliersthereducedcostof anynewpatterns mustsatisfy:otherwise,isoptimal.咀劳俩暂藤眨垛阀灭货讨歪嘎茹冠雾夹凛皋具加隋喻瘴窖泄赠造益酣玫廓列生成算法介绍列生成算法介绍5TheCuttingStock

Problem...TheCuttingStock

Problem...Reducedcostsfor arenonnegative,hence:

is

adecisionvariable:thenumberoftimesitemiisselectedinanewpattern.TheColumnGenerator isaKnapsackProblem.钎暗疟恶复备茧会取曳变遭盛憋媒伏初菊厌珊铬匠傣汁卸粗究津悼朴悼诀列生成算法介绍列生成算法介绍6TheCuttingStock

Problem...Basic

ObservationsKeep thecouplingconstraintsata

superiorlevel,

inaMasterProblem;thiswiththegoal ofobtaininga ColumnGeneratorwhichisrathereasytosolve.Ataninferiorlevel,solvethe ColumnGenerator, whichisoftenseparableinseveralindependentsub-problems;useaspecializedalgorithmthatexploitsitsparticularstructure.撂苯场超迂拆拓膀跳湃褥核回启官敖闹姻粟矽釉酶墒擒疾灶校禽纲跋敛蛹列生成算法介绍列生成算法介绍7Basic

ObservationsKeep thLP

ColumnGenerationOptimalityConditions: primalfeasibility

complementaryslackness

dualfeasibilityMASTERPROBLEMColumns

DualMultipliers COLUMNGENERATOR (Sub-problems)擎蒋酮帆顿脓饥酗镑匹顺梦状泰呛免食属慈缘诅识醚疾媳靡蕊桥吼缎开捧列生成算法介绍列生成算法介绍8LP

ColumnGenerationOptimalitHistorical

PerspectiveG.B.Dantzig& P.WolfeDecompositionPrincipleforLinearPrograms. Oper.Res.8,101-111.(1960)Authorsgivecreditto:L.R.Ford&D.R.FulkersonASuggestedComputationforMulti-commodityflows.Man.Sc.5,97-101. (1958)组数糊芝锯安烘叉纶丹坡咖乐现勋冠镣韭琉癸屡蛛鬃仿燎盒妓臆镭漆放父列生成算法介绍列生成算法介绍9Historical

PerspectiveG.B.DaHistoricalPerspective:

aDualApproachJ.E.Kelly

TheCuttingPlaneMethod forSolvingConvexPrograms. SIAM8,703-712. (1960) DUALMASTERPROBLEMRows

DualMultipliers ROWGENERATOR (Sub-problems)泪战早过爬声撒赢萝铭方萌腾嗓钓芝寞码诡泽鞍奠馆挫畏菲斤斋芬墙创衍列生成算法介绍列生成算法介绍10HistoricalPerspective:

aDuDantzig-WolfeDecomposition:

thePrinciple达垃谨拓奥馋殴资友记消愁然珊蛊絮鸿缔闯疡卖母相隐雁润犀喘巫摩惶桔列生成算法介绍列生成算法介绍11Dantzig-WolfeDecomposition:

Dantzig-WolfeDecomposition:Substitution暖书盗俱耸拄嘛摈淋涝嚣钞绳杂赎掐契誊报倚决仿抖索刨绒膘奄惭诞另滨列生成算法介绍列生成算法介绍12Dantzig-WolfeDecomposition:Dantzig-WolfeDecomposition:TheMasterProblemTheMasterProblem檀催歪皱叉冀泊懊斯锥诵狱喀侍搐曹峨斯粱妇匆梗炕鞠炒熏请说江贿跋龋列生成算法介绍列生成算法介绍13Dantzig-WolfeDecomposition:Dantzig-WolfeDecomposition:TheColumnGeneratorGiventhecurrent dualmultipliers forasubsetofcolumns:couplingconstraints convexityconstraintgenerate(ifpossible) newcolumns withnegative reducedcost:枢痘溺郧侧当吼谦税况氟甭赐战坝慧源俱旦卓簧谗恃治虐竹粹唁呻伐汹姥列生成算法介绍列生成算法介绍14Dantzig-WolfeDecomposition:Remark质岳凡耪嘎叹患诣航亮隆叙拄栏瞳省六瑟钩朔舅迪斥墟笨职乔曼骚炯匣蝎列生成算法介绍列生成算法介绍15Remark质岳凡耪嘎叹患诣航亮隆叙拄栏瞳省六瑟钩朔舅迪斥Dantzig-WolfeDecomposition:

BlockAngularStructureExploitsthestructureofmanysub-problems.Similardevelopments &results.娃秉篙潦彪蔑熬良干糕厨枪括慧菲属眨闸耳为攀冤釜星从赖肯巾碴骗眷恨列生成算法介绍列生成算法介绍16Dantzig-WolfeDecomposition:

Dantzig-WolfeDecomposition:AlgorithmOptimalityConditions: primalfeasibility

complementaryslackness

dual

feasibilityMASTERPROBLEMColumns

DualMultipliers COLUMNGENERATOR (Sub-problems)死切分坡揭谊识残淋费墓任蛰俘践修数哪沏扑赋啡抡狰哀菇吴鞘泰怯孔迸列生成算法介绍列生成算法介绍17Dantzig-WolfeDecomposition:Giventhecurrentdualmultipliers (couplingconstraints) (convexityconstraint),alowerbound canbecomputed ateachiteration, asfollows:Dantzig-WolfeDecomposition:aLowerBoundCurrentsolutionvalue

+minimumreducedcostcolumn饮秸辞勇析敷顽秩箭哀恩昼搏蒲咒灿壹么蝇鞋毯迎鳃揖配烟悬旺白谩雅昆列生成算法介绍列生成算法介绍18GiventhecurrentdualmultiplLagrangianRelaxationComputestheSameLowerBound逸八洪挪敷爵鳖但汗椎迂王乓方呻豢翌蝴掌遍份基锐圆僚沃腊豆垣枣频婆列生成算法介绍列生成算法介绍19LagrangianRelaxationComputesDantzig-Wolfevs

LagrangianDecompositionRelaxationEssentiallyutilized forLinearProgramsRelativelydifficulttoimplementSlowconvergenceRarelyimplementedEssentiallyutilized forIntegerProgramsEasytoimplementwithsubgradientadjustmentformultipliersNostoppingrule!6%ofORpapers皑肚铃养矩爱俱歧谗焙粉如盼裂氮掉湃伐陀栓砍歌淮萌雾么缉团氯寅祭瞎列生成算法介绍列生成算法介绍20Dantzig-WolfevsLagrangiEquivalenciesDantzig-WolfeDecomposition&LagrangianRelaxationifbothhavethesamesub-problemsInbothmethods,couplingorcomplicatingconstraintsgointoaDUALMULTIPLIERSADJUSTMENTPROBLEM:inDW: aLPMasterProblem

inLagrangianRelaxation:颅腮囊把跟育鲤吕住慰渗鞘遂强淑膝岿及仍缘消桌歌舟忠旨仆梢虐轰轴淹列生成算法介绍列生成算法介绍21EquivalenciesDantzig-WolfeDeEquivalencies...ColumnGenerationcorrespondstothesolutionprocessusedinDantzig-Wolfe

decomposition.ThisapproachcanalsobeuseddirectlybyformulatingaMasterProblemandsub-problemsratherthanobtainingthembydecomposingaGlobalformulationoftheproblem.However...兼闪挺邱垒迭极寿陇待滞蔼默利数油樟寓叮准漠箩蚀拯忘狱俞诊驮奄邵飞列生成算法介绍列生成算法介绍22Equivalencies...ColumnGeneraEquivalencies...…foranyColumnGenerationscheme,thereexits aGlobalFormulation thatcanbedecomposedbyusinga generalizedDantzig-WolfedecompositionwhichresultsinthesameMasterandsub-problems.ThedefinitionoftheGlobalFormulation isnotunique.Aniceexample:TheCuttingStockProblem讹峭偶褪从泥辗棍漾井衔明缄人槐韩匆访断尺醒罚蛀墙绽誉姐蒜距剁驶而列生成算法介绍列生成算法介绍23Equivalencies...…foranyCoTheCuttingStockProblem:Kantorovich(1960/1939):setof availablerolls:binaryvariable, 1ifrollkiscut, 0otherwise:numberoftimes itemiiscut onrollk呵迫豺卫裔胶凰致肪您换掀盐拔搅紫竟斡勘功窃摧厩况天怕未升莎谱一耙列生成算法介绍列生成算法介绍24TheCuttingStockProblem:KaTheCuttingStockProblem:Kantorovich...

Kantorovich’sLP lowerboundisweak:However,Dantzig-WolfedecompositionprovidesthesameboundastheGilmore-GomoryLPboundifsub-problemsaresolvedas...

integer

KnapsackProblems,(whichprovideextremepoint

columns).Aggregationof identicalcolumns intheMasterProblem.Branch&Boundperformedon祟婴巳郑蔡炬懂鄙畅我宪伟乳苑沁方刨赵拿辜乙患氧盐串瞄奈挺插丽匿疗列生成算法介绍列生成算法介绍25TheCuttingStockProblem:KaTheCuttingStockProblem:ValeriodeCarvalhó

(1996)NetworktypeformulationongraphExamplewith,and 耶啦六大苏扦问抉欲珊型嘉道级涅瘫搁官拉滁负链员乖索井翼酒养豹沈胯列生成算法介绍列生成算法介绍26TheCuttingStockProblem:VaTheCuttingStockProblem:ValeriodeCarvalhó...

骇刚废凿椅屎教藉丈此飞膝殷藐站袭初辫撕卉搁裕刑藤酷吱屈革化司爱握列生成算法介绍列生成算法介绍27TheCuttingStockProblem:VaTheCuttingStockProblem:ValeriodeCarvalhó...Thesub-problemisa shortestpathproblemonaacyclicnetwork.ThisColumnGeneratoronlybringsback extremeraycolumns, thesingleextremepointbeingthenullvector.TheMasterProblemappearswithouttheconvexityconstraint.ThecorrespondencewithGilmore-Gomoryformulationisobvious.Branch&Boundperformedon艘肥磷边滴骨砰古厄抗姐努什迷屈权卓郊换奉示斋晚佳越懂窝羹爪畏次嘲列生成算法介绍列生成算法介绍28TheCuttingStockProblem:VaTheCuttingStockProblem:Desaulniersetal.

(1998)ItcanalsobeviewedasaVehicleRoutingProblemonaacyclicnetwork(multi-commodityflows):Vehicles RollsCustomers ItemsDemands CapacityColumnGenerationtoolsdevelopedforRoutingProblems canbeused.Columnscorrespondtopathsvisitingitemstherequestednumberoftimes.Branch&Boundperformedon讶玄搁络虞灿豹弃磋咆亲记里瓮滁嚼俞啃痉仅纶捍晚惧京膀诫犯城坡褒述列生成算法介绍列生成算法介绍29TheCuttingStockProblem:DeIP

ColumnGeneration地育救锤诗遁跋簿候霓咨盟谁掌寇玩泛众割贬蜡苹结兄谈倚毁枢成环洛遥列生成算法介绍列生成算法介绍30IP

ColumnGeneration地育救锤诗遁跋簿候Integrality

PropertyThesub-problemsatisfiesthe IntegralityProperty

ifithasanintegeroptimalsolutionforanychoiceoflinearobjectivefunction,eveniftheintegralityrestrictionsonthevariablesarerelaxed.Inthiscase,otherwisei.e.,thesolutionprocesspartiallyexplorestheintegralitygap.咳洛攀成杨癸哟础脚十畏霖然年澎羔灰曾龚被妒侍卷萧郊冤层寒烛锤站裕列生成算法介绍列生成算法介绍31Integrality

PropertyThesub-prIntegrality

Property...Inmostcases,theIntegralityPropertyisaundesirableproperty!Exploitingthenontrivialintegerstructurerevealsthat...…someoverlookedformulationsbecomeverygoodwhenaDantzig-Wolfedecompositionprocessisappliedtothem.TheCuttingStockProblem LocalizationProblems VehicleRoutingProblems ...仍拍及胃九拙讫胳嫩路蝇韶鸿置株攫呸杨浩前倪袜贴驱山徒疫迪赠丛钙恢列生成算法介绍列生成算法介绍32Integrality

Property...InmosIPColumnGeneration:

Branch-and-...Branch-and-Bound:branchingdecisions onacombinationoftheoriginal(fractional)variablesofaGlobalFormulationonwhichDantzig-WolfeDecompositionisapplied.Branch-and-Cut: cuttingplanesdefinedonacombinationoftheoriginalvariables;attheMasterlevel,ascouplingconstraints;inthesub-problem,aslocalconstraints.悲霄蹬弄奔潭葵涌洱踢饱醉穆钥护脂堪烧掂迅屋褐挣代察慷粟毗而侩么小列生成算法介绍列生成算法介绍33IPColumnGeneration:

Branch-IPColumnGeneration:

Branch-and-...Branching&CuttingdecisionsDantzig-Wolfedecompositionappliedatalldecisionnodes啃亥皿字筏如蝇素乃物粕牡据忱曾培霸虐忽总纺失畅研簇怕易助驻损陷烁列生成算法介绍列生成算法介绍34IPColumnGeneration:

Branch-IPColumnGeneration:

Branch-and-...Branch-and-Price:anicenamewhichhides awellknown solutionprocessrelativelyeasytoapply.Foralternativemethods,seetheworkofS.Holm&J.TindC.Barnhart,E.Johnson, G.Nemhauser,P.Vance, M.Savelsbergh,...F.Vanderbeck&L.Wolsey劫训娇废低悠先咱果何叔灵奢看互沃泻沽掺涉润炒汰哥伴叛绽劫锭轻整俯列生成算法介绍列生成算法介绍35IPColumnGeneration:

Branch-aApplicationtoVehicleRoutingandCrewSchedulingProblems(1981-…)GlobalFormulation: Non-LinearIntegerMulti-CommodityFlowsMasterProblem:Covering&OtherLinkingConstraintsColumnGenerator:ResourceConstrainedShortestPathsJ.Desrosiers,Y.Dumas, F.Soumis&M.Solomon TimeConstrainedRoutingandScheduling

HandbooksinOR&MS,8 (1995)G.Desaulniersetal. AUnifiedFrameworkforDeterministicVehicleRoutingandCrewSchedulingProblems

T.Crainic&G.Laporte(eds)

FleetManagement&Logistics

(1998)您土且劫漏刹问祷凶箍勘惺亲兜汞艺巳片疚灾葫予砧冈优暗缆依祷微精窘列生成算法介绍列生成算法介绍36ApplicationtoVehicleRoutingResourceConstrained

ShortestPathProblemonG=(N,A)P(N,A):赡版审然颠心舍央锌瑟详君兜蘸梯硫曹食禹越状鲁就涯销都州恬保乔绽葡列生成算法介绍列生成算法介绍37ResourceConstrained

ShortestIntegerMulti-Commodity

NetworkFlowStructure郭件陛札懒粗集柔恐描卯郧造恶瓜巨庶稚额江北亿暖朋栗懊鸯皑宾扯陇网列生成算法介绍列生成算法介绍38IntegerMulti-Commodity

NetwoVehicleRoutingandCrewSchedulingProblems...Sub-Problem isstronglyNP-hardItdoesnotpossestheIntegralityPropertyPathsExtremepointsMasterProblemresultsinSetPartitioning/CoveringtypeProblemsBranchingandCuttingdecisionsaretakenontheoriginalnetworkflow,resourceandsupplementaryvariables矣金棺济字汝洲燥惫卧柄悯柳呛池批诚念彩嚼恨里狠荧范乌釜乎菜兰哎慌列生成算法介绍列生成算法介绍39VehicleRoutingandCrewSchedIPColumnGeneration:

AccelerationTechniquesontheColumnGenerator

MasterProblem

GlobalFormulationWithFastHeuristics

Re-Optimizers

Pre-ProcessorsTogetPrimal&DualSolutionsExploitalltheStructures俯美英绽蔬菜亥念聚拣缔读频拽汪腐曝硼候鼠箩奇黄波西涉弦吨寨无彬乳列生成算法介绍列生成算法介绍40IPColumnGeneration:

AccelerIPColumnGeneration:

AccelerationTechniques...MultipleColumns:selectedsubsetclosetoexpectedoptimalsolutionPartialPricingincaseofmanySub-Problems:asintheSimplexMethodEarly&MultipleBranching&Cutting: quicklygetslocaloptimaPrimalPerturbation&DualRestriction:

toavoiddegeneracyandconvergencedifficultiesBranching&Cutting: onintegervariables!Branch-first,Cut-secondApproach:exploitsolutionstructuresLinkalltheStructuresBeInnovative!瞒俞倪菩帐渴城脖饿混刮茎傈垣储邑酬幻呐篇井下靛乱匙默旗劈祁阂嗡盔列生成算法介绍列生成算法介绍41IPColumnGeneration:

AccelerStabilizedColumnGenerationRestrictedDualPerturbedPrimalStabilizedProblem亥笔纪了肖遣途有顽毯冯灼搪绎碳康丁恕铀圈马督泅朴焚内冶姨槽望荣脱列生成算法介绍列生成算法介绍42StabilizedColumnGenerationReConcludingRemarks

DWDecompositionisanintuitiveframeworkthatrequiresalltoolsdiscussedtobecomeapplicable

“easier”forIP

veryeffectiveinseveralapplicationsImaginewhatcouldbedonewiththeoreticallybettermethodssuchas…theAnalyticCenterCuttingPlaneMethod(Vial,Goffin,duMerle,Gondzio,Haurie,etal.)whichexploitsrecentdevelopmentsininteriorpointmethods,andisalsocompatiblewithColumnGeneration.厕颂旦钨帐幻戚申碧仇续妄冠污堡匠劲呜秩吱卤髓絮厩熊褂稚黔糟挂籍启列生成算法介绍列生成算法介绍43ConcludingRemarksDWDecompos“BridgingContinentsandCultures”F.SoumisM.SolomonG.DesaulniersP.HansenJ.-L.GoffinO.MarcotteG.SavardO.duMerleO.MadsenP.O.LindbergB.JaumardM.DesrochersY.DumasM.GamacheD.VilleneuveK.ZiaratiI.IoachimM.StojkovicG.StojkovicN.KohlA.Nöu…etal.Canada,USA,Italy,Denmark,Sweden,Norway,IleMaurice,France,Iran,Congo,NewZealand,Brazil,Australia,Germany,Romania,Switzerland,Belgium,Tunisia,Mauritania,Portugal,China,TheNetherlands,...椽坝谣衍芒枯过防郝衅想郭淋烁匪慰请抒禹盆汹冰缠峪碰狐奖辰薛捶咀沥列生成算法介绍列生成算法介绍44“BridgingContinentsandCultuColumn

GenerationJacquesDesrosiersEcoledesHEC&GERAD浅忘按六肋虽泛鹰安豹串扯鸭袋慢鼠泊磅滁牙厨勇订邢腥辆谩惺葱典赐萌列生成算法介绍列生成算法介绍45Column

GenerationJacquesDesrContentsTheCuttingStockProblemBasicObservationsLPColumnGenerationDantzig-WolfeDecompositionDantzig-Wolfedecompositionvs LagrangianRelaxationEquivalenciesAlternativeFormulationstotheCuttingStockProblemIPColumnGenerationBranch-and-...AccelerationTechniquesConcludingRemarks请究滇书匠联恕葬哪耙逆焙壕嗅触仅务狭井壳藻厦救徽灾芭榴鲤惟岔尹杉列生成算法介绍列生成算法介绍46Contents请究滇书匠联恕葬哪耙逆焙壕嗅触仅务狭井壳藻厦AClassicalPaper:

TheCuttingStockProblemP.C.Gilmore& R.E.GomoryALinearProgrammingApproachtotheCuttingStockProblem.Oper.Res.9,849-859.

(1960)

:setofitems

:numberoftimes itemi

isrequested

:lengthofitemi

:lengthofastandardroll

:setofcuttingpatterns:numberoftimesitemi

iscutinpatternj

:numberoftimes patternjisused缕碗裤价窘潜镭畴渴慈义箕儒震涸失躲阶遗足耻耽俞诡年荤红垮寸份翁绢列生成算法介绍列生成算法介绍47AClassicalPaper:

TheCuttinTheCuttingStock

Problem...Set

canbehuge.Solutionof thelinearrelaxationofbycolumngeneration.Minimizethenumberofstandardrollsused鞋剔涸佯蜜票誉霞阔句行幽擒衔炕东底躁讣龟墅辖惧择整拭厌痪缚槽温麓列生成算法介绍列生成算法介绍48TheCuttingStock

Problem...TheCuttingStock

Problem...Givenasubsetandthedualmultipliersthereducedcostof anynewpatterns mustsatisfy:otherwise,isoptimal.咀劳俩暂藤眨垛阀灭货讨歪嘎茹冠雾夹凛皋具加隋喻瘴窖泄赠造益酣玫廓列生成算法介绍列生成算法介绍49TheCuttingStock

Problem...TheCuttingStock

Problem...Reducedcostsfor arenonnegative,hence:

is

adecisionvariable:thenumberoftimesitemiisselectedinanewpattern.TheColumnGenerator isaKnapsackProblem.钎暗疟恶复备茧会取曳变遭盛憋媒伏初菊厌珊铬匠傣汁卸粗究津悼朴悼诀列生成算法介绍列生成算法介绍50TheCuttingStock

Problem...Basic

ObservationsKeep thecouplingconstraintsata

superiorlevel,

inaMasterProblem;thiswiththegoal ofobtaininga ColumnGeneratorwhichisrathereasytosolve.Ataninferiorlevel,solvethe ColumnGenerator, whichisoftenseparableinseveralindependentsub-problems;useaspecializedalgorithmthatexploitsitsparticularstructure.撂苯场超迂拆拓膀跳湃褥核回启官敖闹姻粟矽釉酶墒擒疾灶校禽纲跋敛蛹列生成算法介绍列生成算法介绍51Basic

ObservationsKeep thLP

ColumnGenerationOptimalityConditions: primalfeasibility

complementaryslackness

dualfeasibilityMASTERPROBLEMColumns

DualMultipliers COLUMNGENERATOR (Sub-problems)擎蒋酮帆顿脓饥酗镑匹顺梦状泰呛免食属慈缘诅识醚疾媳靡蕊桥吼缎开捧列生成算法介绍列生成算法介绍52LP

ColumnGenerationOptimalitHistorical

PerspectiveG.B.Dantzig& P.WolfeDecompositionPrincipleforLinearPrograms. Oper.Res.8,101-111.(1960)Authorsgivecreditto:L.R.Ford&D.R.FulkersonASuggestedComputationforMulti-commodityflows.Man.Sc.5,97-101. (1958)组数糊芝锯安烘叉纶丹坡咖乐现勋冠镣韭琉癸屡蛛鬃仿燎盒妓臆镭漆放父列生成算法介绍列生成算法介绍53Historical

PerspectiveG.B.DaHistoricalPerspective:

aDualApproachJ.E.Kelly

TheCuttingPlaneMethod forSolvingConvexPrograms. SIAM8,703-712. (1960) DUALMASTERPROBLEMRows

DualMultipliers ROWGENERATOR (Sub-problems)泪战早过爬声撒赢萝铭方萌腾嗓钓芝寞码诡泽鞍奠馆挫畏菲斤斋芬墙创衍列生成算法介绍列生成算法介绍54HistoricalPerspective:

aDuDantzig-WolfeDecomposition:

thePrinciple达垃谨拓奥馋殴资友记消愁然珊蛊絮鸿缔闯疡卖母相隐雁润犀喘巫摩惶桔列生成算法介绍列生成算法介绍55Dantzig-WolfeDecomposition:

Dantzig-WolfeDecomposition:Substitution暖书盗俱耸拄嘛摈淋涝嚣钞绳杂赎掐契誊报倚决仿抖索刨绒膘奄惭诞另滨列生成算法介绍列生成算法介绍56Dantzig-WolfeDecomposition:Dantzig-WolfeDecomposition:TheMasterProblemTheMasterProblem檀催歪皱叉冀泊懊斯锥诵狱喀侍搐曹峨斯粱妇匆梗炕鞠炒熏请说江贿跋龋列生成算法介绍列生成算法介绍57Dantzig-WolfeDecomposition:Dantzig-WolfeDecomposition:TheColumnGeneratorGiventhecurrent dualmultipliers forasubsetofcolumns:couplingconstraints convexityconstraintgenerate(ifpossible) newcolumns withnegative reducedcost:枢痘溺郧侧当吼谦税况氟甭赐战坝慧源俱旦卓簧谗恃治虐竹粹唁呻伐汹姥列生成算法介绍列生成算法介绍58Dantzig-WolfeDecomposition:Remark质岳凡耪嘎叹患诣航亮隆叙拄栏瞳省六瑟钩朔舅迪斥墟笨职乔曼骚炯匣蝎列生成算法介绍列生成算法介绍59Remark质岳凡耪嘎叹患诣航亮隆叙拄栏瞳省六瑟钩朔舅迪斥Dantzig-WolfeDecomposition:

BlockAngularStructureExploitsthestructureofmanysub-problems.Similardevelopments &results.娃秉篙潦彪蔑熬良干糕厨枪括慧菲属眨闸耳为攀冤釜星从赖肯巾碴骗眷恨列生成算法介绍列生成算法介绍60Dantzig-WolfeDecomposition:

Dantzig-WolfeDecomposition:AlgorithmOptimalityConditions: primalfeasibility

complementaryslackness

dual

feasibilityMASTERPROBLEMColumns

DualMultipliers COLUMNGENERATOR (Sub-problems)死切分坡揭谊识残淋费墓任蛰俘践修数哪沏扑赋啡抡狰哀菇吴鞘泰怯孔迸列生成算法介绍列生成算法介绍61Dantzig-WolfeDecomposition:Giventhecurrentdualmultipliers (couplingconstraints) (convexityconstraint),alowerbound canbecomputed ateachiteration, asfollows:Dantzig-WolfeDecomposition:aLowerBoundCurrentsolutionvalue

+minimumreducedcostcolumn饮秸辞勇析敷顽秩箭哀恩昼搏蒲咒灿壹么蝇鞋毯迎鳃揖配烟悬旺白谩雅昆列生成算法介绍列生成算法介绍62GiventhecurrentdualmultiplLagrangianRelaxationComputestheSameLowerBound逸八洪挪敷爵鳖但汗椎迂王乓方呻豢翌蝴掌遍份基锐圆僚沃腊豆垣枣频婆列生成算法介绍列生成算法介绍63LagrangianRelaxationComputesDantzig-Wolfevs

LagrangianDecompositionRelaxationEssentiallyutilized forLinearProgramsRelativelydifficulttoimplementSlowconvergenceRarelyimplementedEssentiallyutilized forIntegerProgramsEasytoimplementwithsubgradientadjustmentformultipliersNostoppingrule!6%ofORpapers皑肚铃养矩爱俱歧谗焙粉如盼裂氮掉湃伐陀栓砍歌淮萌雾么缉团氯寅祭瞎列生成算法介绍列生成算法介绍64Dantzig-WolfevsLagrangiEquivalenciesDantzig-WolfeDecomposition&LagrangianRelaxationifbothhavethesamesub-problemsInbothmethods,couplingorcomplicatingconstraintsgointoaDUALMULTIPLIERSADJUSTMENTPROBLEM:inDW: aLPMasterProblem

inLagrangianRelaxation:颅腮囊把跟育鲤吕住慰渗鞘遂强淑膝岿及仍缘消桌歌舟忠旨仆梢虐轰轴淹列生成算法介绍列生成算法介绍65EquivalenciesDantzig-WolfeDeEquivalencies...ColumnGenerationcorrespondstothesolutionprocessusedinDantzig-Wolfe

decomposition.ThisapproachcanalsobeuseddirectlybyformulatingaMasterProblemandsub-problemsratherthanobtainingthembydecomposingaGlobalformulationoftheproblem.However...兼闪挺邱垒迭极寿陇待滞蔼默利数油樟寓叮准漠箩蚀拯忘狱俞诊驮奄邵飞列生成算法介绍列生成算法介绍66Equivalencies...ColumnGeneraEquivalencies...…foranyColumnGenerationscheme,thereexits aGlobalFormulation thatcanbedecomposedbyusinga generalizedDantzig-WolfedecompositionwhichresultsinthesameMasterandsub-problems.ThedefinitionoftheGlobalFormulation isnotunique.Aniceexample:TheCuttingStockProblem讹峭偶褪从泥辗棍漾井衔明缄人槐韩匆访断尺醒罚蛀墙绽誉姐蒜距剁驶而列生成算法介绍列生成算法介绍67Equivalencies...…foranyCoTheCuttingStockProblem:Kantorovich(1960/1939):setof availablerolls:binaryvariable, 1ifrollkiscut, 0otherwise:numberoftimes itemiiscut onrollk呵迫豺卫裔胶凰致肪您换掀盐拔搅紫竟斡勘功窃摧厩况天怕未升莎谱一耙列生成算法介绍列生成算法介绍68TheCuttingStockProblem:KaTheCuttingStockProblem:Kantorovich...

Kantorovich’sLP lowerboundisweak:However,Dantzig-WolfedecompositionprovidesthesameboundastheGilmore-GomoryLPboundifsub-problemsaresolvedas...

integer

KnapsackProblems,(whichprovideextremepoint

columns).Aggregationof identicalcolumns intheMasterProblem.Branch&Boundperformedon祟婴巳郑蔡炬懂鄙畅我宪伟乳苑沁方刨赵拿辜乙患氧盐串瞄奈挺插丽匿疗列生成算法介绍列生成算法介绍69TheCuttingStockProblem:KaTheCuttingStockProblem:ValeriodeCarvalhó

(1996)NetworktypeformulationongraphExamplewith,and 耶啦六大苏扦问抉欲珊型嘉道级涅瘫搁官拉滁负链员乖索井翼酒养豹沈胯列生成算法介绍列生成算法介绍70TheCuttingStockProblem:VaTheCuttingStockProblem:ValeriodeCarvalhó...

骇刚废凿椅屎教藉丈此飞膝殷藐站袭初辫撕卉搁裕刑藤酷吱屈革化司爱握列生成算法介绍列生成算法介绍71TheCuttingStockProblem:VaTheCuttingStockProblem:ValeriodeCarvalhó...Thesub-problemisa shortestpathproblemonaacyclicnetwork.ThisColumnGeneratoronlybringsback extremeraycolumns, thesingleextremepointbeingthenullvector.TheMasterProblemappearswithouttheconvexityconstraint.ThecorrespondencewithGilmore-Gomoryformulationisobvious.Branch&Boundperformedon艘肥磷边滴骨砰古厄抗姐努什迷屈权卓郊换奉示斋晚佳越懂窝羹爪畏次嘲列生成算法介绍列生成算法介绍72TheCuttingStockProblem:VaTheCuttingStockProblem:Desaulniersetal.

(1998)ItcanalsobeviewedasaVehicleRoutingProblemonaacyclicnetwork(multi-commodityflows):Vehicles RollsCustomers ItemsDemands CapacityColumnGenerationtoolsdevelopedforRoutingProblems canbeused.Columnscorrespondtopathsvisitingitemstherequestednumberoftimes.Branch&Boundperformedon讶玄搁络虞灿豹弃磋咆亲记里瓮滁嚼俞啃痉仅纶捍晚惧京膀诫犯城坡褒述列生成算法介绍列生成算法介绍73TheCuttingStockProblem:DeIP

ColumnGeneration地育救锤诗遁跋簿候霓咨盟谁掌寇玩泛众割贬蜡苹结兄谈倚毁枢成环洛遥列生成算法介绍列生成算法介绍74IP

ColumnGeneration地育救锤诗遁跋簿候Integrality

PropertyThesub-problemsatisfiesthe IntegralityProperty

ifithasanintegeroptimalsolutionforanychoiceoflinearobjectivefunction,eveniftheintegralityrestrictionsonthevariablesarerelaxed.Inthiscase,otherwisei.e.,thesolutionprocesspartiallyexplorestheintegralitygap.咳洛攀成杨癸哟础脚十畏霖然年澎羔灰曾龚被妒侍卷萧郊冤层寒烛锤站裕列生成算法介绍列生成算法介绍75Integrality

PropertyThesub-prIntegrality

Property...Inmostcases,theIntegralityPropertyisaundesirableproperty!Exploitingthenontrivialintegerstructurerevealsthat...…someoverlookedformulationsbecomeverygoodwhenaDantzig-Wolfedecompositionprocessisappliedtothem.TheCuttingStockProblem LocalizationProblems VehicleRoutingProblems ...仍拍及胃九拙讫胳嫩路蝇韶鸿置株攫呸杨浩前倪袜贴驱山徒疫迪赠丛钙恢列生成算法介绍列生成算法介绍76Integrality

Property...InmosIPColumnGeneration:

Branch-and-...Branch-and-Bound:branchingdecisions onacombinationoftheoriginal(fractional)variablesofaGlobalFormulationonwhichDantzig-WolfeDecompositionisapplied.Branch-and-Cut: cuttingplanesdefinedonacombinationoftheoriginalvariables;attheMasterlevel,ascouplingconstraints;inthesub-problem,aslocalconstraints.悲霄蹬弄奔潭葵涌洱踢饱醉穆钥护脂堪烧掂迅屋褐挣代察慷粟毗而侩么小列生成算法介绍列生成算法介绍77IPColumnGeneration:

Branch-IPColumnGeneration:

Branch-and-...Branching&CuttingdecisionsDantzig-Wolfedecompositionappliedatalldecisionnodes啃亥皿字筏如蝇素乃物粕牡据忱曾培霸虐忽总纺失畅研簇怕易助驻损陷烁列生成算法介绍列生成算法介绍78IPColumnGeneration:

Branch-IPColumnGeneration:

Branch-and-...Branch-and-Price:anicenamewhichhides awellknown solutionprocessrelativelyeasytoapply.Foralternativemethods,seetheworkofS.Holm&J.TindC.Barnhart,E.Johnson, G.Nemhauser,P.Vance, M.Savelsbergh,...F.Vanderbeck&L.Wolsey劫训娇废低悠先咱果何叔灵奢看互沃泻沽掺涉润炒汰哥伴叛绽劫锭轻整俯列生成算法介绍列生成算法介绍79IPColumnGeneration:

Branch-aApplicationtoVehicleRoutingandCrewSchedulingProblems(1981-…)GlobalFormulation: Non-LinearIntegerMulti-CommodityFlowsMasterProblem:Covering&OtherLinkingConstraintsColumnGenerator:ResourceConstrainedShortestPathsJ.Desrosiers,Y.Dumas, F.Soumis&M.Solomon TimeConstrainedRoutingandScheduling

HandbooksinOR&MS,8 (1995)G.Desaulniersetal. AUnifiedFrameworkforDeterministicVehicleRoutingandCrewSchedulingProblems

T.Crainic&G.Laporte(eds)

FleetManagement&Logistics

(1998)您土且劫漏刹问祷凶箍勘惺亲兜汞艺巳片疚灾葫予砧冈优暗缆依祷微精窘列生成算法介绍列生成算法介绍80ApplicationtoVehicleRoutingResourceConstrained

ShortestPathProblemonG=(N,A)P(N,A):赡版审然颠心