Min-degree constrainedminimumspanningtreeproblem:Newformulationvia Miller–Tucker–Zemlin constraints

Given anundirectednetworkwithpositiveedgecostsandapositiveinteger d>2, the minimum-degree constrained minimumspanningtreeproblem is theproblemoffindingaspanningtreewithminimum total costsuchthateachnon-leafnodeinthetreehasadegreeofatleast d. Thisproblemisnewtothe literature whiletherelatedproblemwithupperboundconstraintsondegreesiswellstudied.Mixed- integer programsproposedforeithertypeofproblemiscomposed,ingeneral,ofa tree-defining part and a degree-enforcing part. Inourformulationoftheminimum-degreeconstrainedminimumspanningtree problem, thetree-definingpartisbasedontheMiller–Tucker–Zemlinconstraintswhiletheonlyearlier paper availableintheliteratureonthisproblemusessingleandmulti-commodityflow-basedformula- tions thatarewellstudiedforthecaseofupperdegreeconstraints.Weproposeanewsetofconstraints for thedegree-enforcingpartthatleadtosignificantlybettersolutiontimesthanearlierapproacheswhen used inconjunctionwithMiller–Tucker–Zemlinconstraints.