New formulationsforthehop-constrainedminimumspanningtreeproblem via SheraliandDriscoll’stightenedMiller–Tucker–Zemlinconstraints

Given anundirectednetworkwithpositiveedgecostsandanaturalnumber p, thehop-constrained minimumspanningtreeproblem(HMST)istheproblemoffindingaspanningtreewithminimumtotal cost suchthateachpathstartingfromaspecifiedrootnodehasnomorethan p hops (edges).Inthis paper,thenewmodelsbasedontheMiller–Tucker–Zemlin(MTZ)subtoureliminationconstraintsare developedandcomputationalresultstogetherwithcomparisonsagainstMTZ-based,flow-based,and hop-indexedformulationsarereported.ThefirstmodelisobtainedbyadaptingtheMTZ-based AsymmetricTravelingSalesmanProblemformulationofSheraliandDriscoll [18] and theothertwo modelsareobtainedbycombiningtopology-enforcingandMTZ-relatedconstraintsofferedbyAkg ¨un and Tansel(submittedforpublication) [20] for HMSTwiththefirstmodelappropriately.Computational studiesshowthatthebestLPboundsoftheMTZ-basedmodelsintheliteratureareimprovedbythe proposedmodels.ThebestsolutiontimesoftheMTZ-basedmodelsarenotimprovedforoptimally solvedinstances.However,theresultsfortheharder,large-sizeinstancesimplythattheproposed modelsarelikelytoproducebettersolutiontimes.Theproposedmodelsdonotdominatetheflow- based andhop-indexedformulationswithrespecttoLPbounds.However,goodfeasiblesolutionscan be obtainedinareasonableamountoftimeforproblemsforwhicheventheLPrelaxationsoftheflow- based andhop-indexedformulationscanbesolvedinabout2days.