Min-degree constrained minimum spanning tree problem: New formulation via Miller-Tucker-Zemlin constraints
COMPUTERS & OPERATIONS RESEARCH, cilt.37, sa.1, ss.72-82, 2010 (SCI-Expanded)
- 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.