Abstract
In a previous paper, Gouveia and Magnanti (2003) 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 in Gouveia and Magnanti (2003). Moreover, the new model permits us to solve large Euclidean problem instances that are not solvable by prior approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abdalla, A., N. Deo, and R. Fraceschini. (1999). “Parallel Heuristics for the Diameter-Constrained Minimum Spanning Tree Problem.” Congressus Numeratium, 136, 97–118.
Achuthan, N.R., L. Caccetta, P. Caccetta, and J.F. Geelen. (1992). “Algorithms for the Minimum Weight Spanning Tree with Bounded Diameter Problem.” In P.K.H. Phua, C.M. Wang, W.Y. Yeong, T.Y. Leong, H.T. Loh, K.C. Tan, and F.S. Chou (eds.), Optimization: Techniques and Applications, Vol. 1. World Scientific Publishing, pp. 297–304.
Achuthan, N.R., L. Caccetta, P. Caccetta, and J.F. Geelen. (1994). “Computational Methods for the Diameter Restricted Minimum Weight Spanning Tree Problem.” Australasian Journal of Combinatorics 10, 51–71.
Garey, M. and D. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco.
Gouveia, L. (1998). “Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints.” INFORMS Journal on Computing, 10, 180–188.
Gouveia, L. and T. Magnanti. (2003). “Network Flow Models for Designing Diameter Constrained Spanning and Steiner Trees.” Networks, 41, 159–173.
Gouveia, L, T. Magnanti, and C. Requejo. (2004). “A 2-Path Approach for Odd-Diameter-Constrained Minimum Spanning and Steiner Trees.” Networks, 44, 254–265.
Magnanti, T. and L. Wolsey. (1996). “Optimal Trees” in “Network Models.” Handbooks in Operations Research and Management Science, 7, 503–615.
Magnanti, T. and R. Wong. (1984). “Network Design and Transportation Planning: Models and Algorithms.” Transportation Science, 18, 1–55.
Woolston, K. and S. Albin. (1988). “The Design of Centralized Networks with Reliability and Availability Constraints.” Computers and Operations Research, 15, 207–217.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research funded in part by the Research Projects POCTI-ISFL-1-152,POSI/CPS/41459/2001 and POCTI/MAT/139/94
Research funded in part by the Singapore-MITAlliance(SMA)
Rights and permissions
About this article
Cite this article
Gouveia, L., Magnanti, T.L. & Requejo, C. An intersecting tree model for odd-diameter-constrained minimum spanning and Steiner trees. Ann Oper Res 146, 19–39 (2006). https://doi.org/10.1007/s10479-006-0049-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-006-0049-0