New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Creative Commons License

Akgun I., Tansel B. C.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.212, sa.2, ss.263-276, 2011 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 212 Sayı: 2
  • Basım Tarihi: 2011
  • Doi Numarası: 10.1016/j.ejor.2011.01.051
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.263-276
  • Anahtar Kelimeler: Graph theory, Integer programming, Spanning trees, Hop constraints, Miller-Tucker-Zemlin constraints, FLOW MODELS, NETWORKS, DESIGN
  • Abdullah Gül Üniversitesi Adresli: Hayır

Özet

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, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991). (C) 2011 Elsevier B.V. All rights reserved.