treeproblemwithintervaldata
R.Montemanni∗,L.M.Gambardella
IstitutoDalleMollediStudisull’IntelligenzaArtificiale(IDSIA)
Galleria2,CH-6928Manno-Lugano,Switzerland
Abstract
Therobustspanningtreeproblemisavariation,motivatedbytelecommunicationsapplications,oftheclassicminimumspanningtreeproblem.Intherobustspanningtreeproblemedgecostslieinanintervalinsteadofhavingafixedvalue.
Intervalnumbersmodeluncertaintyabouttheexactcostvalues.Arobustspan-ningtreeisaspanningtreewhosetotalcostminimizesthemaximumdeviationfromtheoptimalspanningtreeoverallrealizationsoftheedgecosts.Thisrobustnessconceptisformalizedinmathematicaltermsandisusedtodriveoptimization.
Inthispaperabranchandboundalgorithmfortherobustspanningtreeproblemisproposed.Themethodembedstheextensionofsomeresultspreviouslypresentedintheliteratureandsomenewelements,suchasanewlowerboundandsomenewreductionrules,allbasedontheexploitationofsomepeculiaritiesofthebranchingstrategyadopted.
Computationalresultsobtainedbythealgorithmarepresented.Thetechniqueweproposeisupto210fasterthanmethodsrecentlyappearedintheliterature.Keywords:Branchandbound,robustoptimization,intervaldata,spanningtreeproblem.
1Introduction
Thispaperpresentsabranchandboundalgorithmforarobustversionoftheminimumspanningtreeproblemwhereedgecostslieinanintervalinsteadofhavingafixedvalue.Eachintervalisusedtomodeluncertaintyabouttherealvalueoftherespectivecost,whichcantakeanyvalueintheinterval,independentlyfromthecostsassociatedwiththeotheredgesofthegraph.
Adoptingthemodeldescribedabove,theclassicoptimalitycriterionoftheminimumspanningtreeproblem(whereafixedcostisassociatedwitheachedgeofthegraph)doesnotapplyanymore,andtheclassicpolynomial-timealgorithms(Kruskal[9]andPrim[11])cannotbeused.Amorecomplexoptimizationcriterionhasthentobeadopted.Wehavechosentherelativerobustnesscriterion(seeKouvelisandYu[7]).
Thestudyhaspracticalmotivations,andinparticulartherearesomeapplicationsinthefieldoftelecommunications.Considerasupervisornodeinadatanetworkwheretransmissionlinesaresubjecttouncertaindelays,thatwantstosendacontrolmessagetoallothernodesinthenetwork.Thesupervisornodegenerallywantstobroadcastthemessageoverarobustspanningtree,inordertohavearelativelyquickbroadcastwhateverthesituationinthenetworkis(seeBertsekasandGallagher[3]foramoredetailed
∗Corresponding
author.Tel.+41916108568.Fax:+41916108661.Email:roberto@idsia.ch
1
descriptionoftheproblem).Asecondapplicationconcernsthedesignofcommunicationnetworkswhereroutingdelaysonedgesareuncertain,sincetheydependonthenetworktraffic.Theidealnetworkguaranteesgoodperformancewhateveristherealtraffic,i.e.arobustspanningtreeisdesirable(seeKouvelisandYu[7]formoredetails).
Intheliteraturetherearesomeotherstudiesrelatedtorobustversionsoftheminimumspanningtreeproblem.KozinaandPerepelista[8]definedanorderrelationonthesetoffeasiblesolutionsandgeneratedaParetoset.AronandVanHentenryck[2]provedthattheproblemisNP-hard.InYamanetal.[12]amixedintegerprogrammingformulationandapreprocessingtechniquearepresented.
Thepresentpaperdescribesabranchandboundalgorithm,basedonanadaptationofthemethoddevelopedinMontemannietal.[10]fortherobustshortestpathproblem.Thealgorithmincorporatesanextensionofthepreprocessingrulesdescribedin[12]andsomenewconceptswhichsignificantlycontributetotheefficiencyofthemethod.
AnotherbranchandboundapproachtotherobustspanningtreeproblemhasbeenindependentlydevelopedbyAronandVanHentenryck(see[1]).Fromanalgorithmicpointofview,themethodtheyproposehasweakerpreprocessingandreductionrules,alessefficientbranchingstrategyandsharesthesamelowerbound.
InSection2therobustspanningtreeproblemwithintervaldataisformallydescribed.Section3isdevotedtothepresentationofthenewbranchandboundalgorithmanditscomponents.Section4isdedicatedtocomputationalresults,whileconclusionsarepresentedinSection5.
2Problemdescription
TherobustspanningtreeproblemwithintervaldataisdefinedonagraphG={V,E},whereVisasetofverticesandEisasetofedges.Aninterval[lij,uij],with0≤lij Definition2.Therobustdeviationforaspanningtreetinascenariosisthedifferencebetweenthecostoftinsandthecostoftheminimumspanningtreeins. Definition3.Aspanningtreetissaidtobearelativerobustspanningtreeifithasthesmallest(amongallspanningtrees)maximum(amongallpossiblescenarios)robustdeviation. Ascenariocanbeseenasasnapshotofthenetworksituation,whilearelativerobustspanningtree(robustspanningtreeforshort)isatreewhichminimizesthemaximumdeviationfromtheoptimalspanningtreeoverallrealizationsoftheedgecosts. Thefollowingresult(see[12])isusedbythemethodwepropose: Givenaspanningtreet,ascenarios(t)whichmakestherobustdeviationmaximumfor s(t)s(t) tistheonewherecij=uij∀{i,j}∈tandckh=lkh∀{k,h}∈E\. Intheremainderofthispaperwewillrefertothescenarios(t)asthescenarioinducedbytreet.Wewillalsorefertothecostoftins(t)minusthecostins(t)ofaminimumspanningtreeofs(t)asRCost(t),therobustnesscostoft. Apolynomial-timeprocedurefortheevaluationoftherobustnesscostofagivenspan-ningtreetarises.Itsimplyworksbysubtractingthecostoftheminimumspanningtreeinscenarios(t)(Prim[11])fromthecost,inthesamescenario,oft. 2 3ThebranchandboundalgorithmBB-RST BB-RST,aBranchandBoundalgorithmfortheRobustSpanningTreeproblemwithintervaldata,ispresentedinthispaper.ItisanadaptationofanalgorithmrecentlypresentedinMontemannietal.[10].TheelementsofthealgorithmaredescribedinSections3.1to3.5.Apseudo-codeforthemethodispresentedinSection3.6,togetherwithastudyofthecomputationalcomplexityofthealgorithm. 3.1Structureofthesearch-treenode Fromnowon,wewillrefertothesearch-treesubtreerootedinnodedasSubT(d).Eachnodedofthesearch-treeisthenidentifiedbythefollowingelements: •in(d):listofedges.Theedgescontainedinin(d)mustappearinallofthespanningtreesassociatedwiththesearch-treenodesofSubT(d);•out(d):listofedges.Theedgescontainedinout(d)areforbiddenforallofthespanningtreesassociatedwiththesearch-treenodesofSubT(d); •t(d):spanningtreeassociatedwiththesearch-treenoded.t(d)isaspanningtree s(u) withminimumcostinscenarios(u)(i.e.thescenariowherecij=uij∀{i,j}∈E)amongthosewhichrespectthelimitationsimposedbyedgesetsin(d)andout(d),i.e.t(d)mustcontaintheedgesinin(d)andcannotincludetheedgesinout(d);•lb(d):lowerboundfortherobustnesscostofthespanningtreesassociatedwiththesearch-treenodesinSubT(d).ThecalculationofthelowerboundisdescribedinSection3.4. 3.2Preprocessing Therulesdescribedinthefollowingsectionsaretobeappliedbeforethebranchandboundprocedurestarts,inordertosimplifytheproblem.3.2.1 RuleP1 Yamanetal.[12]provedthatarobustspanningtreecontainsonlyedgeswhichlieonsomeminimumspanningtreeforsomescenario(weakedges).Theyconsequentlydonotconsidernon-weakedgeswhenlookingforarobustspanningtree.Astrongerresultisgiveninthispaper. Theorem1.Anon-weakedgeecanbedeletedfromgraphGwhensolvingarobustspan-ningtreeproblem. Proof.From[12]weknowthatewillnotbeinanyrobustspanningtreetofG.Theminimumspanningtreeinscenarios(t)isaweaktreebydefinition,andconsequentlyitcannotcontainedgee. WecanconcludethatecanbedeletedfromEbecauseitwillbeneitherinanyrobusttreenorintheminimumspanningtreesofthescenariosinducedbythem. Theorem1isstrongerbecauseitstatesthatitispossibletodeleteanon-weakedgeinsteadofsimplynotconsideringitwhenlookingforarobustspanningtree. 3 3.2.2RuleP2 Observation1.Anedgewhichliesonsomeminimumspanningtreeforeachscenario(strongedge),canbeinsertedintotheedgesetin(r),whereristherootofthesearch-tree.Observation1followsdirectlyfrom[12]andfromthebranchingruleadoptedbyBB-RST(seeSection3.3). 3.3Branchingstrategy Therootrofthesearch-treeisthenodewithout(r)=∅,in(r)={e|eisastrongedge}andlb(r)=0.InitiallyrwillbetheonlynodecontainedinS,thesetofthenodestobeexamined.DuringtheexecutionofBB-RST,variableubTreewillcontainthebestspanningtree(intermsofrobustness)foundsofar. AteachiterationofBB-RST,thenotyetexaminednodedwiththesmallestvalueoflb(d)isselectedand,ifdisnotaleafofthesearch-tree(i.e.in(d)=t(d)),anedgee∈t(d)\\in(d)isselected(asdescribedinSection3.3.1)inordertocreatetwonewsearch-treenodes.Thefirstnewsearch-treenode,d,hasin(d)=in(d)andout(d)=out(d)∪{e}.Thesecondone,d,hasin(d)=in(d)∪{e}andout(d)=out(d).ThereductionrulesdescribedinSection3.5areappliedtodinordertoenlargethearcsetout(d).Thevaluesoflb(d)andlb(d)arecalculatedasdescribedinSection3.4.Iflb(d)≥RCost(ubTree)thennodediscut,iflb(d)≥RCost(ubTree)thennodediscut.Itiseasytoseethatt(d)=t(d),whilethecomputationoft(d)isdescribedinSection3.3.1.IncaseRCost(t(d)) Themethodweproposefortheselectionofedgeeautomaticallyproducest(d).ThisisakeyfactorintheperformanceobtainedbyalgorithmBB-RST.Thestrategyweuseisbasedonthefollowingtheorem,whichisageneralizationofaresultpresentedinGabow[6]. Theorem2.LetH={VH,EH}beagivenintervalgraphandletsbeascenario.Lettbethespanningtreewithminimumcostinscenariosamongthosewhichin-cludetheedgesofagivenedgesetB.Letebeanedgeint\\B.IfwedefineF= s {g∈EH\\{e}|t\\{e}∪{g}isaspanningtree}andf=argming∈Fcg,then,ifF=∅,t\\{e}∪{f}isaspanningtreeofgraphK={VH,EH\\{e}},andithastheminimumcostinscenariosamongthespanningtreesofKwhichincludetheedgesintheedgesetB.Proof.Lett=t\\{e}∪{f}.SupposetdoesnothaveminimumcostinscenariosamongtreesonHwhichincludetheedgesinB.Thenthereexistsg∈t\\Bandh∈EHsuchthatt=t\\{g}∪{h}isaspanningtreeofH,tincludestheedgesofBandthasa s smallercostthantinscenarios,i.e.csh Edgehalsojoinstaandtb.Forifnot,assumewithoutlossofgeneralitythathjoins s twoverticesofta.Thisimplies(definitionofh)thatalsogisinta.Ascsh ss cs(1)f≤ch Assumenow,withoutlossofgenerality,thatg∈ta.Nowletta\\{g}consistoftwonewtrees,tcandtd.Edgeeisincidenttooneofthesetrees,saytc.Sincet\\{e}\\{g}∪{f}∪{h}isaspanningtree,eitherforhisincidenttotc.So,eithert\\{g}∪{f}ort\\{g}∪{h}isaspanningtree.Butequation(1)impliesthatbothofthesespanningtreeshaveacostlessthantinscenarios,acontradictiontothehypothesis.ThustheoriginalassumptionisfalseandthasminimumcostinscenariosamongtreesthatincludetheedgesinB. UsingTheorem2,itispossibletoderivethefollowingresult. Corollary1.Givenasearch-treenodedandselectedanedgee∈t(d)\\in(d),thenthe s(u) spanningtreeinthenodedist(d)=t(d)\\{e}∪{f},wheref=argminh∈FechandFe={h∈E\\out(d)\\{e}|t\\{e}∪{h}isaspanningtree}. Proof.Weobservethattheedgescontainedinout(d)cannotbecontainedinanyspanningtreeassociatedwiththesearch-treenodesinSubT(d).Thenwecandefine,inthecontextofTheorem2,H={V,E\\out(d)}andscenariosasscenarios(u).Consequentlyt=t(d).Now,givene∈t(d)\\in(d),Theorem2statesthatt=t(d)\\{e}∪{f},withfdefinedasinthehypothesis,isaspanningtreewithminimumcostinscenarios(u)(amongthosethatincludetheedgesinin(d)=in(d))forthegraphK={V,E\\out(d)}.Wecanthenconcludethatt(d)=t. ThetheoreticalresultofCorollary1isusedtoselectedgeeinanintelligentway. s(u)s(u) e:=argmaxminch−cg(2) g∈t(d)\\in(d)h∈Ag whereAg={h∈E\\out(d)\\{g},suchthatt\\{g}∪{h}isaspanningtreeofG}.The s(u) edgeenteringint(d)isthenf=argminh∈Aech.Thecostinscenarios(u)oft(d)isgreaterthanorequaltothecostoft(d)inthesamescenariobecausech−ce≥0bydefinition. Theevaluationof(2)isveryquick,becausecheckingwhetherthesubstitutionofanedgeinaspanningtreeproducesanotherspanningtreeisaveryeasytaskfromacomputationalpointofview.Selectionrule(2)guaranteesthatt(d)hasthehighestpossiblecostinscenarios(u).ThisencouragesthepruningofSubT(d). s(u) s(u) 3.4Lowerbound ThelowerboundwepresentisbasedonthesameideaasthatdescribedinMontemannietal.[10]. Tobetterdescribethelowerbound,weneedtogivethefollowingdefinitions.Sce-s(B)s(B) narios(B)isthescenariowherecij=uij∀{i,j}∈Bandcij=lij∀{i,j}∈E\\B.CostST(s,in,out)isthecostoft,thespanningtreeinscenarioswiththeminimumcostsuchthattincludesalltheedgesintheedgesetinandtdoesnotcontaintheedgesintheedgesetout. Givenasearch-treenoded,wecanthendefine: lb(d):=CostST(s(E),in(d),out(d))−CostST(s(E\\out(d)),∅,∅) (3) Practicallylb(d)isthecostinscenarios(u)oft(d)minusthecostoftheminimumcostspanningtreeofthescenariowheretheedgesinout(d)areattheirlowerboundsandtheotheredgesareattheirupperbounds.Atheoreticaljustificationforthedefinitiongivenin(3)isguaranteedbythefollowingresult:Theorem3.CostST(s(E),in(d),out(d))RCost(t(p))∀p∈SubT(d) 5 − CostST(s(E\\out(d)),∅,∅) ≤ Proof.BydefinitionoffunctionRCostwehave: RCost(t(p))=CostST(s(E),in(p),out(p))−CostST(s(t(p)),∅,∅) (4) Asin(d)⊆in(p)∀p∈SubT(d)andout(d)⊆out(p)∀p∈SubT(d)bydefinitionofthebranchingrule(seeSection3.3),wehave: CostST(s(E),in(d),out(d))≤CostST(s(E),in(p),out(p))∀p∈SubT(d) (5) Wealsoknowthatt(p)⊆E\\out(p)∀p∈SubT(d).IfweconsiderthistogetherwiththedefinitionoffunctionCostST,wehave: CostST(s(E\\out(d)),∅,∅)≥CostST(s(t(p)),∅,∅)∀p∈SubT(d) Wecanconclude: CostST(s(E),in(d),out(d))−CostST(s(E\\out(d)),∅,∅)≤RCost(t(p))∀p∈SubT(d) (7) (6) 3.5Reductionrules Inthissectionsomereductionrules,usedwhenanewsearch-treenodediscreated,aredescribed.Therulesincreasethedimensionofout(d).ThisisacrucialfactorforalgorithmBB-RST,becausethelowerboundlb(d)istighterwhenout(d)islarger(seeSection3.4).3.5.1 RuleR1 Observation2.Givenanodedofthesearch-tree,if{i,j},{j,k}∈in(d)then{i,k}canbeinsertedintoout(d). Observation2holdsbecauset(p)isatree,anditcannotcontaincycles.{i,j},{j,k}∈t(p)∀p∈SubT(d)bydefinitionofin(d).Consequently∀p∈SubT(d){i,k}cannotbeint(p).Then{i,k}canbeinsertedintoout(d).TheruleisanadaptationofthatdescribedinMontemannietal.[10].3.5.2 RuleR2 ReductionruleR2isbasedonageneralizationofthepreprocessingruleP1,presentedinSection3.2.1.Todescribeit,wedefineanin(d)-spanningtreeasaspanningtreewhichincludesalltheedgesofin(d),andanin(d)-weakedgeasanedgewhichliesonsomein(d)-spanningtreewhichhasminimumcostinsomescenario. Theorem4.Giveanodedofthesearch-tree,ifedgeeisanon-in(d)-weakedge,thenecanbeinsertedintoout(d). Proof.Eachrobustspanningtreeisaweaktree,i.e.aminimumspanningtreeforsomescenario(Yamanetal.[12]).Eachweaktreethatincludestheedgesofin(d)(ifitexists)mustbeain(d)-weaktree,i.e.musthave,forsomescenario,minimumcostamongspanningtreeswhichincludetheedgescontainedinin(d).Thenonlyin(d)-weaktreescouldberobustspanningtrees.Consequentlyallnon-in(d)-weakedgescanbeinsertedintoout(d),becausetheywillnotappearinanyrobustspanningtree. Thefollowingcharacterizationforin(d)-weakedgescanthenbegiven. 6 Theorem5.Givenasearch-treenoded,edgeeisain(d)-weakedgeifandonlyifthereexistsain(d)-spanningtreeofminimumcostwhichusesedgeewhenthecostofedgeeisatitslowerboundandthecostsoftheremainingedgesareattheirupperbounds.Proof.Ifthereexistsain(d)-spanningtreethatusesedgeeandhasminimumcost(amongin(d)-spanningtrees)inthescenariodefinedinthehypothesis,thenedgeeisain(d)-weakedgebydefinition. Weprovetheconversebyshowingthatiftheredoesnotexistaminimumin(d)-spanningtreethatusesedgeeforthestatedscenario,thenecannotbeain(d)-weakedge. ConsiderKruskal’salgorithm[9]whichsortsalledgesinnon-decreasingorderoftheircosts,anddefineL,thesetofedgeschosentoformaminimumspanningtree.Kruskal’salgorithmproceedsasfollows.Initially,thesetLisempty.ThealgorithmexamineseachedgeinthesortedorderinturnandcheckswhetheraddingthecurrentedgetosetLcreatesacyclewiththeedgesalreadyinL.Ifitdoesnot,thecurrentedgeisaddedtoL,otherwiseitisdiscarded.Thealgorithmstopswhentherearen−1edgesinL.Incaseoftiesinthesortedorder,anedgemaybechosenarbitrarilyfromamongstthosewithleastcost. WemodifyKruskal’salgorithmslightly.FirstweinitializeL=in(d),forcingtheedgesofin(d)tobeincludedinthespanningtreereturnedbythealgorithm.Wealsoaskthatincaseofties,thealgorithmfavorsedgeeoverotheredgestoaddtoL.Withthislastmodification,itcanbeshownthatifeisnotonthespanningtreefoundbythealgorithmforaparticularscenario,thenitisnotonanyminimumin(d)-spanningtreeforthatscenario.Letsbethescenariodefinedinthehypothesis,i.e.withcostonedgeeatitslowerboundandallothercostsattheirupperbounds.Wenowshowthatifeisnotonanyminimumin(d)-spanningtreeforscenarios,thenitcannotbeonanyminimumin(d)-spanningtreeunderanyscenario,andsoitmustbethatedgeeisnotain(d)-weakedge. LetLsdenotethespanningtreereturnedbythemodifiedalgorithmappliedtothegraphunderscenarios.Ifeisnotonanyminimumin(d)-spanningtreeforscenarios,thenitisnotonthespanningtreefoundbythealgorithmforscenarios,soeither|Ls|reachesn−1beforeeisencounteredinthesortedorder,oraddingetoLsatthepointitwasencounteredinthesortedorderwouldintroduceacycle.LetCdenotetheedges insuchacycle.Nowsupposethereisascenariossuchthate∈Ls.LetDdenote thesetofedgese∈C\\{e}suchthate∈/Ls.ClearlyD=∅andC\\D⊆Ls.For eachedgee∈D,sinceitwasnotaddedtoLs,itmustbethateformsacyclewith s edgesalreadyinLtheedgesinsuchacycle.Nowitisnothardtosee:letCedenotesthat(C\\D)∪e∈DCe\\{e}inducesacyclewithalledgesinthesetL.Thisisa contradiction,sinceLsformsatree,soecannotlieonaminimumin(d)-spanningtreeforscenariosfoundbythealgorithm,foranyscenarios. Furthermore,byourmodificationofKruskal’salgorithm,wehavethatecannotlieonanyminimumin(d)-spanningtreeunderanyscenarios,andhenceecannotbeain(d)-weakedge. TheproofofTheorem5suggestsaprocedurewithcomputationalcomplexityO(|E|log|E|)(modificationofKruskal’salgorithm[9])tocheckwhetheranedgeeisin(d)-weakornot.Thisprocedureisanalogoustothatusedtocheckwhetheranedgeisweak(strong)ornot(see[12]). 3.6Pseudo-codeandcomputationalcomplexity ThebranchandboundalgorithmBB-RSTissummarizedinFigure1,whereapseudo-codeispresented. 7 01:02:03:04:05:06:07:08:09:10:11:ApplyrulesP1andP2andinitializer;//ristherootofthesearch-treeS:={r};//Sisthesetofsearch-treenodestobevisitedubTree:=t(r);//ubTreeisthebesttreeretrievedsofarWhile(S=∅) Selectd∈Ssuchthatlb(d)≤lb(p)∀p∈SandextractdfromS;If(disnotasearch-treeleaf) Selecte∈t(d)\\in(d)andcreatedanddasdescribedinSection3.3;ApplyrulesR1andR2tod;Calculatelb(d)andlb(d); EventuallyadddanddtoSandupdateubTree; ReturnubTree; Figure1:Apseudo-codeforthebranchandboundalgorithmBB-RST. Table1:Definitionoftheproblems. LUk kSet1[0,10)(le,10]Set2[0,15)(le,15]Set3[0,20)(le,20]Set4[0,10)(le,20]Set5[0,15)(le,30]Set6[0,20)(le,40] Thepseudo-codealsohelpstoestimatethecomputationalcomplexityofalgorithmBB-RST. Theorem6.ThecomputationalcomplexityofalgorithmBB-RSTisO(|V||V|−1|E|2log|E|).Proof.Givenasearch-treenoded,thespanningtreet(d)cannotbeassociatedwiththenodesinSubT(d)becauseoneoftheedgesoft(d)isinout(d).t(d)canbeassociatedwithatmost|V|−1search-treenodesofachainofd-typenodes,withthecorrespondinginsetsincrementallyincreasingfrom∅tot(d).Sincetherearenomorethan|V||V|−2spanningtreesforagraphG(Cayley[4]),thesearch-treenodesexaminedinlines05−10ofthepseudo-codearenomorethan(|V|−1)|V||V|−2.Themostexpensiveoperationcarriedoutforeachsearch-treenodeistheoneatline08,andhasacomputationalcomplexityofO(|E|2log|E|)(Yamanetal.[12]).ThecomputationalcomplexityofalgorithmBB-RSTisconsequentlyO(|V||V|−1|E|2log|E|) Itisimportanttopointoutthatnotwithstandingthisveryhighcomputationalcom-plexity,algorithmBB-RSTisveryefficientinpractice(seeSection4). 4Computationalresults WetestourmethodonthesamefamiliesofproblemsusedinYamanetal.[12]andonsomenewproblemswehavegenerated. In[12]completegraphswith|V|=10,15,20and25areconsidered.Forproblemswith|V|=10,15and20sixsetsoffiveproblemseacharegenerated,accordinglytothefollowingdefinition.EachsetkisdefinedbytwointervalsLkandUk,summarizedinTable1.Foreachproblemofsetk,∀e∈E,leisrandomlyselectedfromLkanduefromUk.Forthecase|V|=25onlyfivetestproblemsfromset1areconsidered,becauseofthelongcomputationtimes. Wecompareourresultswiththoseobtainedbysolvingthemixedintegerprogramde-scribedin[12],preprocessedasdescribedinthesamepaperandwiththoseofthebranch 8 Table2:Computationalresults1. |V|10152025 Yamanetal.[12]1.9633.09693.882027.60 Yamanetal.new0.85286.47>2016.28>3600.00 AronandVanHentenryck[1] 0.284.6069.95610.45 BB-RST0.041.8456.46484.24 andboundalgorithmpresentedinAronandVanHentenryck[1],whereadifferentimple-mentationoftheproceduretoretrieveweak(andB-weak)edgesisalsoproposed. Werandomlygeneratedthefamiliesofbenchmarkswiththesamespecificationsusedin[12],andwerepeatedexactlythesametestspresentedthere.Theproblemsconsideredarenotnecessarilythesameusedin[12],becauseofthepresenceofarandomfactorintheircreation.Fortheresultspresentedin[12],aPentiumIIPC450MHzandILOGCPLEX16.5.1wereused,whileforthispaperaPentiumIIPC400MHzandCPLEX6.0areused.Theresultspresentedin[1]areobtainedonaSunSparc440MHzcomputer,whichisabout2.5timesfasterthantheourmachine(Dongarra[5]).ThisratiowillbeusedtocomparetheresultswiththoseofBB-RST.Foreachfamilyofproblems,inTable2wepresenttheresultsreportedin[12](Yamanetal.[12]),theresultsobtainedbythemethoddescribedin[12]inourtests(Yamanetal.new),theresultspresentedin[1]fortheequivalentofourbranchandboundalgorithm(AronandVanHentenryck[1])andtheresultsobtainedbyalgorithmBB-RST(BB-RST).Themaximumcomputationtimeforeachrunhasbeenfixedat3600seconds.Afterthistimethecomputationisstopped,unlessithasalreadyterminated.ThishappenedforsometestssummarizedinthelasttworowsofthethirdcolumnofTable2(entriescontaining“>”).Inthesecasesacontributeof3600secondshasbeencountedinordertoobtaintheaveragesreportedinthetable.Table2showsthat,asexpected,usingthenewapproachdescribedinthispaperstronglyimprovestheresultspresentedin[12].BB-RSTismuchfasterthanthemethodsuggestedin[12],evenwhentheresultsofBB-RSTarecomparedwiththosereportedin[12],whichareobtained,aspointedoutbefore,onamuchfastercomputer.BB-RSTisalsomoreefficientthantheequivalentbranchandboundalgorithmdescribedin[1].Since,asobservedbefore,thetwomethodssharethesamelowerbound,butourapproachhasbranchingstrategy,preprocessingandreductionruleswithasoundertheoreticaljustification,thisresultwasexpected. Asecondsetofbenchmarksisconsidered.Alltheproblemsarecompletegraphsandhave20verticesrandomlyplacedona50×50grid.∀{i,j}∈E,lijisrandomlyselectedin[edij(1−p),edij)anduijin(lij,edij(1+p)],whereedijistheeuclidiandistancebetweeniandj,andpisadistortionparameter.Weconsiderthreedifferentvaluesforp:0.15,0.50and0.85.Foreachofthesevaluesofp,fiveproblemshavebeengeneratedandsolvedwiththetechniqueproposedin[12](Yamanetal.)andwiththealgorithmdescribedinthispaper(BB-RST).Theaverageoftheresultsobtained,thistimeonaSUNWUltra-30computer(withCPLEX6.0),arepresentedinTable3.ThegapbetweenthecomputationtimesofthetwomethodsismuchwiderthaninTable2.ThishappensbecauseBB-RSTtakesadvantageoftheeuclidianstructureoftheproblems.Boththealgorithmsworkbetterwhenpishighbecausespanningtreeshave,inthiscase,morescatteredrobustnesscosts. 1www.cplex.com. 9 Table3:Computationalresults2.p0.150.500.85 Yamanetal.320.9161.4133.74 BB-RST1.530.730.46 5Conclusion Therobustspanningtreeproblem,whichcanbeusedtomodelinmathematicaltermssometelecommunicationsproblems,hasbeenstudiedinthispaper. Abranchandboundalgorithmforthisproblemhasbeendescribed.Itcombinestheextensionofresultspreviouslypresentedintheliteraturewithsomenewelements,suchasanewlowerboundwhichworksbyexploitingsomepropertiesconnectedwiththead-hocbranchingrulewehavedeveloped.Somenewreductionrules,againbasedontheexploitationofsomepeculiaritiesofthebranchingruleadopted,contributetospeedupthemethod. Computationalresultsprovethatthealgorithmweproposeisverycompetitive.Itstronglyimprovestheresultsobtainedbymethodsthathaverecentlyappearedinthelit-erature. Acknowledgements Thisworkwasco-fundedbytheEuropeanCommissionISTproject“MOSCA:DecisionSupportSystemForIntegratedDoor-To-DoorDelivery:PlanningandControlinLogisticChain”,grantIST-2000-29557.TheinformationprovidedisthesoleresponsibilityoftheauthorsanddoesnotreflecttheCommunity’sopinion.TheCommunityisnotresponsibleforanyusethatmightbemadeofdataappearinginthispublication. References [1]I.AronandP.VanHentenryck.Aconstraintssatisfactionapproachtotherobust spanningtreeproblemwithintervaldata.Inpreparation.ComputerScienceDepart-ment,BrownUniversity,May2002.[2]I.AronandP.VanHentenryck.Onthecomplexityoftherobustspanningtreewith intervaldata.OperationsResearchLetters,toappear.[3]D.P.BertsekasandR.Gallagher.DataNetworks.Prentice-Hall,EnglewoodCliffs, NJ,1987.[4]A.Cayley.Atheoremontrees.QuarterlyJournalofPureandAppliedMathematics, 23:376–378,1889.[5]J.J.Dongarra.Performanceofvariouscomputersusingstandardlinearalgebrasoft-wareinafortranenvironment.TechnicalReportCS-89-85,UniversityofTennessee,July2003.[6]H.N.Gabow.Twoalgorithmsforgeneratingweightedspanningtreesinorder.SIAM JournalonComputing,6(1):139–150,March1977. 10 [7]P.KouvelisandG.Yu.RobustDiscreteOptimizationanditsapplications.Kluwer AcademicPublishers,1997.[8]G.L.KozinaandV.A.Perepelista.Intervalspanningtreesproblem:solvabilityand computationalcomplexity.IntervalComputations,1:42–50,1994.[9]J.B.Kruskal.Ontheshortestspanningsubtreeofagraphandthetravellingsalesman problem.PreceedingsoftheAmericanMathematicalSociety,7:48–50,1956.[10]R.Montemanni,L.M.Gambardella,andA.V.Donati.Abranchandboundalgorithm fortherobustshortestpathproblemwithintervaldata.OperationsResearchLetters,toappear.[11]R.C.Prim.Shortestconnectionnetworksandsomegeneralizations.BellSystem TechnicalJournal,36:1389–1401,1957.[12]H.Yaman,O.E.Kara¸san,andM.C¸.Pinar.Therobustspanningtreeproblemwith intervaldata.OperationsResearchLetters,29:31–40,2001. 11 因篇幅问题不能全部显示，请点此查看更多更全内容