Min-degree constrained minimum spanning tree problem: New formulation via Miller-Tucker-Zemlin constraints

Creative Commons License

Akgun I., Tansel B. C.

COMPUTERS & OPERATIONS RESEARCH, cilt.37, sa.1, ss.72-82, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 37 Sayı: 1
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1016/j.cor.2009.03.006
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.72-82
  • Anahtar Kelimeler: Mixed integer programming, Degree-enforcing constraints, Miller-Tucker-Zemlin constraints, Minimum spanning tree, Flow formulation, Rooted arborescence
  • Abdullah Gül Üniversitesi Adresli: Hayır

Özet

Given an undirected network with positive edge costs and a positive integer d > 2, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least d. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller-Tucker-Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller-Tucker-Zemlin constraints. (C) 2009 Elsevier Ltd. All rights reserved.