An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees

An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees

0.00 Avg rating0 Votes
Article ID: iaor20071421
Country: Netherlands
Volume: 146
Issue: 1
Start Page Number: 19
End Page Number: 39
Publication Date: Sep 2006
Journal: Annals of Operations Research
Authors: , ,
Keywords: networks: flow
Abstract:

In a previous paper, Gouveia and Magnanti found diameter-constrained minimal spanning and Steiner tree problems to be more difficult to solve when the tree diameter D is odd. In this paper, we provide an alternate modeling approach that views problems with odd diameters as the superposition of two problems with even diameters. We show how to tighten the resulting formulation to develop a model with a stronger linear programming relaxation. The linear programming gaps for the tightened model are very small, typically less than 0.5–, and are usually one third to one tenth of the gaps of the best previous model described by Gouveia and Magnanti. Moreover, the new model permits us to solve large Euclidean problem instances that are not solvable by prior approaches.

Reviews

Required fields are marked *. Your email address will not be published.