Abstract
In this paper we propose a hybrid memory adaptive heuristic for solving the Capacitated Minimum Spanning Tree (CMST) problem. We augment the problem formulation with additional non-redundant constraints via use of adaptive memory, to improve upon the performance of an elementary heuristic (the Esau-Williams heuristic). Our methodology is tested against many of the previously reported heuristics for the CMST. We conclude that our generalized procedure performs on par with the best of these approaches in terms of solution quality, while expending a very modest amount of computational effort.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Altinkemer, K. and B. Gavish. (1988). “Heuristics with Constant Error Guarantees for the Design of Tree Networks,” Management Science 34(3), 331–341.
Amberg, A., W. Domschke, and S. Voss. (1996). “Capacitated Minimum Spanning Trees: Algorithms Using Intelligent Search,” Combinatorial Optimization: Theory and Practice 1(1).
Esau, L.R. and K.C. Williams. (1966). “On Teleprocessing Systems Design, Part II—AMethod for Approximating the Optimal Network,” IBM Systems Journal 5(3), 142–147.
Fleurent, C. and F. Glover. (1999). “Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory,” INFORMS Journal of Computing, forthcoming.
Gavish, B. (1982). “Topological Design of Centralized Computer Networks—Formulations and Algorithms,” Networks 12, 355–377.
Gavish, B. (1983). “Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem,” Journal of the Association of Computing Machinery 30, 118–132.
Gavish, B. (1985). “Augmented Lagrangian Based Algorithms for Centralized Network Design,” IEEE Trans. Communications 33, 1247–1257.
Gavish, B. and K. Altinkemer. (1986). “Parallel Saving Heuristics for the Topological Design of Local Access Tree Networks.” Proc. Of IEEE INFOCOM’ 86, Fifth Annual Conference on Computers and Communications Integration Design, Analysis, Management, pp. 130–139.
Glover, F. (1965). “A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem,” Operations Research 13, 879–919.
Glover, F. (1977). “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences 8, 156–166.
Glover, F. (1997). “Tabu Search and Adaptive Memory Programming—Advances, Applications and Challenges.” In R.S. Barr, R.V. Helgason, and J.L Kennington (eds.), Advances in Metaheuristics, Optimization, and Stochastic Modeling Technologies. Boston, MA: Kluwer Academic Publisher.
Gouveia, L. (1993). “A Comparison of Directed Formulations for the Capacitated Minimum Spanning Tree Problem,” Telecommunications Systems 1, 51–76.
Gouveia, L. (1995). “A 2in Constraint Formulation for the Capacitated Minimum Spanning Tree Problem,” Operations Research 43, 130–141.
Gouveia, L. and J. Paixão. (1991). “Dynamic Programming Based Heuristics for the Topological Design of Local Access Networks,” Annals of Operations Research 33, 305–327.
Gouveia, L. and P. Martins. (1999). “The Capacitated Minimum Spanning Tree Problem: An Experiment with a Hop-Indexed Model,” Annals of Operations Research 86, 271–294.
Hall, L. (1996). “Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem,” INFORMS Journal on Computing 8(3), 219–234.
Karnaugh, M. (1976). “A New Class of Algorithms for Multipoint Network Optimization,” IEEE Transactions on Communications 24(5), 500–505.
Kershenbaum, A., R. Boorstyn, and R. Oppenheim. (1980). “Second-Order Greedy Algorithms for Centralized Network Design,” IEEE Transactions on Communications 22(11), 1835–1838.
Kershenbaum, A. and.W Chou. (1974). “AUnified Algorithm for Designing Multidrop Teleprocessing Networks,” IEEE Transactions on Communications 22(11).
Papadimitriou, C.H. (1978). “The Complexity of the Capacitated Tree Problem,” Networks 4, 217–230.
Rolland, E., R. Patterson, and B. Dodin. (1998). “A Memory Adaptive Reasoning Technique for Solving the Audit Scheduling Problem,” Financial Accounting Abstracts Working Paper Series, June 8. Working Paper No. WP1998-002, Center for Advanced Information and Telecommunication Technology Applications, School of Management, The University of Texas at Dallas, Richardson, TX.
Sharaiha, Y.M.,M. Gendreau, G. Laporte, and I.H. Osman. (1997). “A Tabu Search Algorithm for the Capacitated Shortest Spanning Tree Problem,” Networks 29, 161–171.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Patterson, R., Pirkul, H. & Rolland, E. A Memory Adaptive Reasoning Technique for Solving the Capacitated Minimum Spanning Tree Problem. Journal of Heuristics 5, 159–180 (1999). https://doi.org/10.1023/A:1009629727566
Issue Date:
DOI: https://doi.org/10.1023/A:1009629727566