New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints

Creative Commons License

Akgun I.

COMPUTERS & OPERATIONS RESEARCH, vol.38, no.1, pp.277-286, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 38 Issue: 1
  • Publication Date: 2011
  • Doi Number: 10.1016/j.cor.2010.05.003
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.277-286
  • Keywords: Miller-Tucker-Zemlin constraints, Spanning trees, Network flows, Integer programming, Hop constraints, FLOW MODELS, NETWORKS, DESIGN
  • Abdullah Gül University Affiliated: No


Given an undirected network with positive edge costs and a natural number p, the hop-constrained minimum spanning tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, the new models based on the Miller-Tucker-Zemlin (MTZ) subtour elimination constraints are developed and computational results together with comparisons against MTZ-based, flow-based, and hop-indexed formulations are reported. The first model is obtained by adapting the MTZ-based Asymmetric Traveling Salesman Problem formulation of Sherali and Driscoll [18] and the other two models are obtained by combining topology-enforcing and MTZ-related constraints offered by Akgun and Tansel (submitted for publication) [20] for HMST with the first model appropriately. Computational studies show that the best LP bounds of the MTZ-based models in the literature are improved by the proposed models. The best solution times of the MTZ-based models are not improved for optimally solved instances. However, the results for the harder, large-size instances imply that the proposed models are likely to produce better solution times. The proposed models do not dominate the flow-based and hop-indexed formulations with respect to LP bounds. However, good feasible solutions can be obtained in a reasonable amount of time for problems for which even the LP relaxations of the flow-based and hop-indexed formulations can be solved in about 2 days. (C) 2010 Elsevier Ltd. All rights reserved.