Generalized network design problems. (English) Zbl 1036.90026

Feremans, Corinne; Labbé, Martine; Laporte, Gilbert

Eur. J. Oper. Res. 148, No. 1, 1-13 (2003).

Summary: Network design problems (NDP) consist of identifying an optimal subgraph of a graph, subject to side constraints. In generalized NDP, the vertex set is partitioned into clusters and the feasibility conditions are expressed in terms of the clusters. Several applications of generalized NDP arise in the fields of telecommunications, transportation and biology. The aim of this review article is to formally define generalized NDP, to study their properties and to provide some applications.

MSC:

90B10	Deterministic network models in operations research
90C27	Combinatorial optimization

Keywords:

Combinatorial optimization; Network design

Software:

SteinLib

References:

[1]	Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flows: Theory, Algorithms, and Applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2]	Althaus, E.; Kohlbacher, O.; Lenhof, H.-P.; Müller, P., A combinatorial approach to protein docking with flexible side chains, (Shamir, R.; Miyano, S.; Istrail, S.; Pevzner, P.; Waterman, M., Proceedings of the 4th Annual International Conference on Computational Molecular Biology (RECOMB-00) (2000), ACM Press), 15-24
[3]	Asef-Vaziri, A.; Laporte, G.; Sriskandarajah, C., The block layout shortest loop problem, IIE Transactions, 32, 727-734 (2000)
[4]	Chopra, S., On the spanning tree polyhedron, Operations Research Letters, 8, 25-29 (1989) · Zbl 0675.90060
[5]	Chopra, S.; Rao, M. R., The Steiner tree problem I: Formulations, compositions and extension of facets, Mathematical Programming, 64, 209-229 (1994) · Zbl 0821.90124
[6]	Chopra, S.; Rao, M. R., The Steiner tree problem II: Properties and classes of facets, Mathematical Programming, 64, 231-246 (1994) · Zbl 0831.90115
[7]	Christofides, N., Worst-case analysis of a new heuritic for the traveling salesman problem, (Management Science Research Report, vol. 388 (1976), Carnegie Mellon University: Carnegie Mellon University Pittsburgh)
[8]	Cook, W. J.; Cunningham, W. H.; Pulleyblank, W. R.; Schrijver, A., Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization (1998), Wiley: Wiley New York · Zbl 0909.90227
[9]	Dimitrijević, V.; Saric, Z., An efficient transformation of the generalized traveling salesman problem into traveling salesman problem on digraphs, Information Sciences, 102, 105-110 (1997) · Zbl 0918.90134
[10]	Dror, M.; Haouari, M., Generalized Steiner problems and other variants, Journal of Combinatorial Optimization, 4, 415-436 (2000) · Zbl 0980.90074
[11]	Dror, M.; Haouari, M.; Chaouachi, J., Generalized spanning trees, European Journal of Operational Research, 120, 583-592 (2000) · Zbl 0985.90076
[12]	Dror, M.; Laporte, G.; Louveaux, F. V., Vehicle routing with stochastic demands and restricted failures, Zeitschrift für Operations Research, 37, 273-283 (1993) · Zbl 0804.90040
[13]	Duin, C. W.; Volgenant, A., Some generalizations of the Steiner tree in graphs, Networks, 17, 353-364 (1987) · Zbl 0644.90088
[14]	U. Faigle, W. Kern, P.C. Pop, G. Still, The Generalized Minimum Spanning Tree Problem, Working Paper, Department of Operations Research and Mathematical Programming, University of Twente, http://www.math.utwente.nl/dos/ormp/preprints.htm; U. Faigle, W. Kern, P.C. Pop, G. Still, The Generalized Minimum Spanning Tree Problem, Working Paper, Department of Operations Research and Mathematical Programming, University of Twente, http://www.math.utwente.nl/dos/ormp/preprints.htm · Zbl 1409.05059
[15]	C. Feremans, Generalized spanning trees and extensions, Ph.D. dissertation, Université Libre de Bruxelles, 2001; C. Feremans, Generalized spanning trees and extensions, Ph.D. dissertation, Université Libre de Bruxelles, 2001 · Zbl 0990.90120
[16]	Feremans, C.; Labbé, M.; Laporte, G., On generalized minimum spanning trees, European Journal of Operational Research, 134, 457-458 (2001) · Zbl 0990.90120
[17]	Feremans, C.; Labbé, M.; Laporte, G., A comparative analysis of several formulations for the generalized minimum spanning tree problem, Networks, 39, 29-34 (2002) · Zbl 1001.90066
[18]	Fischetti, M.; Salazar, J. J.; Toth, P., The symmetric generalized traveling salesman polytope, Networks, 26, 113-123 (1995) · Zbl 0856.90116
[19]	Fischetti, M.; Salazar, J. J.; Toth, P., A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Operations Research, 45, 378-394 (1997) · Zbl 0893.90164
[20]	Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[21]	Garg, N.; Konjevod, G.; Ravi, R., A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, 37, 66-84 (2000) · Zbl 0962.68136
[22]	Gillard, P.; Yang, B., The class Steiner minimal tree problem: A lower bound and test problem generation, Acta Informatica, 37, 193-211 (2000) · Zbl 0962.68176
[23]	Goemans, M. X.; Myung, Y. S., A catalog of Steiner tree formulations, Networks, 23, 19-28 (1993) · Zbl 0794.90074
[24]	Goemans, M. X., The Steiner tree polytope and related polyhedra, Mathematical Programming, 63, 157-182 (1994) · Zbl 0808.90124
[25]	E. Gorres. On the node weighted Steiner tree problem. Ph.D. dissertation, New York University, 1992; E. Gorres. On the node weighted Steiner tree problem. Ph.D. dissertation, New York University, 1992 · Zbl 0759.90091
[26]	Grötschel, M.; Monma, C. L.; Stoer, M., Design of survivable networks, (Ball, M. O.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Handbooks in Operations Research and Management Science (Chapter 10), vol. 7 (1995), Elsevier: Elsevier Amsterdam), 617-672 · Zbl 0839.90132
[27]	Helvig, C. S.; Robins, G.; Zelikovsky, A., An improved approximation scheme for the group Steiner problem, Networks, 37, 8-20 (2001) · Zbl 0997.90096
[28]	Henry-Labordere, A. L., The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem, RIRO, B-2, 43-49 (1969) · Zbl 0187.14002
[29]	D. Huygens. Version Généralisée du Problème de Conception de Réseau 2-Arê te-Connexe. Mémoire de Licence en Sciences Mathématiques, Faculté des Sciences, Université Libre de Bruxelles, 2000; D. Huygens. Version Généralisée du Problème de Conception de Réseau 2-Arê te-Connexe. Mémoire de Licence en Sciences Mathématiques, Faculté des Sciences, Université Libre de Bruxelles, 2000
[30]	Ihler, E., Bounds on the quality of approximate solutions to the group Steiner tree problem, (Graph-Theoretic Concepts in Computer Science WG90, Lecture Notes in Computer Science, vol. 484 (1991), Springer), 109-118 · Zbl 0768.68045
[31]	Ihler, E.; Reich, G.; Widmayer, P., Class Steiner trees and VLSI-design, Discrete Applied Mathematics, 90, 173-194 (1999) · Zbl 0921.68054
[32]	Klein, P.; Ravi, R., A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, 19, 104-115 (1995) · Zbl 0836.68046
[33]	Koch, T.; Martin, A., Solving the Steiner tree problems in graphs to optimality, Networks, 32, 207-232 (1998) · Zbl 1002.90078
[34]	A.M.C.A. Koster. Frequency assignment models and algorithms, Ph.D. dissertation, Proefschrift Universiteit Maastricht, 1999; A.M.C.A. Koster. Frequency assignment models and algorithms, Ph.D. dissertation, Proefschrift Universiteit Maastricht, 1999
[35]	Koster, A. M.C. A.; Van Hoesel, S. P.M.; Kolen, A. W.J., The partial constraint satisfaction problem: Facets and lifting theorems, Operations Research Letters, 23, 89-97 (1998) · Zbl 0957.90095
[36]	Labbé, M.; Laporte, G., Maximizing user convenience and postal service efficiency in post box location, Belgian Journal of Operations Research, Statistics and Computer Science, 26, 22-35 (1986)
[37]	Laporte, G., Location routing problems, (Golden, B. L.; Assad, A. A., Vehicle Routing: Methods and Studies (1988), North-Holland: North-Holland Amsterdam), 163-197 · Zbl 0644.90030
[38]	Laporte, G.; Asef-Vaziri, A.; Sriskandarajah, C., Some applications of the generalized traveling salesman problem, Journal of the Operational Research Society, 47, 1461-1467 (1996) · Zbl 0873.90104
[39]	Laporte, G.; Chapleau, S.; Landry, P.-É.; Mercure, H., An algorithm for the design of mailbox collection routes in urban area, Transportation Research, 23B, 271-280 (1989)
[40]	Laporte, G.; Nobert, Y., Generalized traveling salesman problem through \(n\) sets of nodes: An integer programming approach, INFOR, 21, 61-75 (1983) · Zbl 0524.90069
[41]	Laporte, G.; Semet, F., Computational evaluation of a transformation procedure for the symmetric generalized traveling salesman problem, INFOR, 37, 114-120 (1999) · Zbl 07677583
[42]	(Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (1985), Wiley: Wiley New York) · Zbl 0562.00014
[43]	Li, W.-J.; Tsao, J.; Ulular, O., The shortest path with at most \(l\) nodes in each of the series/parallel clusters, Networks, 26, 263-271 (1995) · Zbl 0856.90047
[44]	Lien, Y. N.; Ma, E.; Wah, B. W.S., Transformation of the generalized traveling salesman into the standard traveling salesman problem, Information Sciences, 74, 177-189 (1993) · Zbl 0790.90073
[45]	Magnanti, T. L.; Wolsey, L. A., Optimal trees, (Ball, M. O.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Handbooks in Operations Research and Management Science (Chapter 9), vol. 7 (1995), Elsevier Science: Elsevier Science Amsterdam), 503-615 · Zbl 0839.90135
[46]	Mahjoub, A. R., Two-edge connected spanning subgraphs and polyhedra, Mathematical Programming, 64, 199-208 (1994) · Zbl 0820.90117
[47]	Myung, Y. S.; Lee, C. H.; Tcha, D. W., On the generalized minimum spanning tree problem, Networks, 26, 231-241 (1995) · Zbl 0856.90117
[48]	Noon, C. E.; Bean, J. C., A Lagrangian based approach for the asymmetric generalized traveling salesman problem, Operations Research, 39, 623-632 (1991) · Zbl 0741.90086
[49]	Noon, C. E.; Bean, J. C., An efficient transformation of the generalized travelling salesman problem, INFOR, 31, 39-44 (1993) · Zbl 0774.90085
[50]	C.E. Noon, The generalized traveling salesman problem, Ph.D. dissertation, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1988; C.E. Noon, The generalized traveling salesman problem, Ph.D. dissertation, Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, 1988
[51]	P.C. Pop, W. Kern, G.J. Still. An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size, Working Paper, Department of Operations Research and Mathematical Programming, University of Twente, http://www.math.utwente.nl/dos/ormp/preprints.htm; P.C. Pop, W. Kern, G.J. Still. An approximation algorithm for the generalized minimum spanning tree problem with bounded cluster size, Working Paper, Department of Operations Research and Mathematical Programming, University of Twente, http://www.math.utwente.nl/dos/ormp/preprints.htm
[52]	(Reich, G.; Widmayer, P., Beyond Steiner’s problem: A VLSI oriented generalization, Graph Theoretic Concepts in Computer Science WG89, Lecture Notes in Computer Science, vol. 411 (1990), Springer), 196-210 · Zbl 0768.68176
[53]	Renaud, J.; Boctor, F. F., An efficient composite heuristic for the symmetric generalized traveling salesman problem, European Journal of Operational Research, 108, 571-584 (1998) · Zbl 0944.90068
[54]	Renaud, J.; Boctor, F. F.; Laporte, G., A fast composite heuristic for the symmetric traveling salesman problem, INFORMS Journal on Computing, 4, 134-143 (1996) · Zbl 0866.90131
[55]	Salazar González, J.-J., A note on the generalized Steiner tree polytope, Discrete Applied Mathematics, 100, 137-144 (2000) · Zbl 0947.90065
[56]	Saskena, J. P., Mathematical model of scheduling clients through welfare agencies, Journal of the Canadian Operational Research Society, 8, 185-200 (1970) · Zbl 0211.52002
[57]	Segev, A., The node-weighted Steiner tree problem, Networks, 17, 1-17 (1987) · Zbl 0645.90092
[58]	P. Slavı́k. On the approximation of the generalized traveling salesman problem, Working Paper, Department of Mathematics, University of Buffalo, 1997; P. Slavı́k. On the approximation of the generalized traveling salesman problem, Working Paper, Department of Mathematics, University of Buffalo, 1997
[59]	L. Snyder, M.S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem, Working Paper, Department of Industrial Engineering and Management Sciences, Northwestern University, http://users.iems.nwu.edu/lsnyder/papers/gtsp.html; L. Snyder, M.S. Daskin. A random-key genetic algorithm for the generalized traveling salesman problem, Working Paper, Department of Industrial Engineering and Management Sciences, Northwestern University, http://users.iems.nwu.edu/lsnyder/papers/gtsp.html
[60]	Srivastava, S. S.; Kumar, S.; Garg, R. C.; Sen, P., Generalized traveling salesman problem through \(n\) sets of nodes, Journal of the Canadian Operational Research Society, 7, 97-101 (1969) · Zbl 0174.51305
[61]	Winter, P., Steiner problem in networks: A survey, Networks, 17, 129-167 (1987) · Zbl 0646.90028