A branch and cut method for the degree-constrained minimum spanning tree problem. (English) Zbl 0967.90094
Summary: A problem of interest in network design is that of finding, in a given weighted graph, a minimum-weight spanning tree whose vertices satisfy specified degree restrictions. We present a branch and cut solution procedure for this NP-complete problem. Our algorithm is implemented and extensively tested. Computational results on 3150 random table problems ranging from 100 to 800 vertices are presented and discussed.
MSC:
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C27 | Combinatorial optimization |
| 90C11 | Mixed integer programming |
| 90B10 | Deterministic network models in operations research |
| 05C35 | Extremal problems in graph theory |
Keywords:
branch and cut; combinatorial optimization; optimal trees; mixed integer linear programming; network designSoftware:
CPLEXReferences:
| [1] | Achuthan, Eur J Oper Res 91 pp 573– (1995) |
| [2] | and An improved branch and cut algorithm for the capacitated vehicle routing problem, submitted for publication. |
| [3] | Applegate, Doc Math (J Deutsch Mathe-Vereinigung) Int Congr Math pp 6450– (1998) |
| [4] | and Computational results with a branch and cut code for the capacitated vehicle routing problem, Research Report 949-M, Universite Joseph Fourier, Grenoble, France, (1995). |
| [5] | ?Graph theory in network design and analysis?, Recent studies in graph theory, (Editor), Vishwa International, India, (1989), 29-63. |
| [6] | and Heuristics for the degree restricted spanning tree problem, submitted for publication. |
| [7] | Christofides, Math Program 20 pp 255– (1981) |
| [8] | CPLEX Optimization Inc., Using the CPLEX Callable Library and CPLEX Mixed Integer Library, 930 Tahoe Blvd # 802-297, Incline Village, NV 89451, 1993. |
| [9] | Dijkstra, Num Math 1 pp 269– (1959) |
| [10] | Gabow, Combinatorica 6 pp 109– (1986) |
| [11] | and Computers and interactibility, A guide to the theory of NP-completeness Freeman, San Francisco, 1979. |
| [12] | Gavish, Networks 12 pp 355– (1982) |
| [13] | Branch and cut methods for the symmetric capacitated vehicle routing, PhD Thesis, Curtin University of Technology, Perth, Western Australia, 1995. |
| [14] | Kruskal, Proc Am Math Soc 7 pp 48– (1956) |
| [15] | Laporte, Oper Res 33 pp 1050– (1985) |
| [16] | Narula, Comput Oper Res 7 pp 239– (1980) |
| [17] | Padberg, SIAM Rev 33 pp 60– (1991) |
| [18] | Prim, BSTJ 36 pp 1389– (1957) |
| [19] | Savelsbergh, Comput Oper Res 12 pp 341– (1985) |
| [20] | Volgenant, Eur J Oper Res 39 pp 325– (1989) |
| [21] | Volgenant, Eur J Oper Res 12 pp 394– (1983) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
