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, vol.37, no.1, pp.72-82, 2010 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 37 Issue: 1
  • Publication Date: 2010
  • Doi Number: 10.1016/j.cor.2009.03.006
  • Journal Name: COMPUTERS & OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.72-82
  • Keywords: Mixed integer programming, Degree-enforcing constraints, Miller-Tucker-Zemlin constraints, Minimum spanning tree, Flow formulation, Rooted arborescence
  • Abdullah Gül University Affiliated: No

Abstract

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.