Chapter 9
Network Design Problems: Fundamental Methods
Alain Quilliot,
Alain Quilliot
LIMOS, University of Blaise-Pascal, Clermont-Ferrand, France
Search for more papers by this authorAlain Quilliot,
Alain Quilliot
LIMOS, University of Blaise-Pascal, Clermont-Ferrand, France
Search for more papers by this authorBook Editor(s):Vangelis Th. Paschos,
Vangelis Th. Paschos
LAMSADE, University of Paris-Dauphine, France
Search for more papers by this authorFirst published: 13 February 2013
Summary
This chapter contains sections titled:
-
Introduction
-
The main mathematical and algorithmic tools for network design
-
Models and problems
-
The STEINER-EXTENDED problem
-
Conclusion
-
Bibliography
Bibliography
- [AHU 01] AHUJA R.K., ORLIN J.B., SHARMA D., “Multiexchange neighbourhood structures for the capacitated minimum spanning tree problem”, Math. Programming 91, p 71--97, 2001.
- [AHU 95] AHUJA R.K., MAGNANTI T.L., ORLIN J.B., REDDY M.R., “Applications of network optimization”, Chapter 1 of Network Models, Handbook of Operation Research and Management Science 7, p 1--83, 1995.
- [AHU 93] AHUJA R.K., MAGNANTI T.L., ORLIN J.B., Network Flows: Theory, Algorithms and Applications, Prentice hall, Englewood Cliffs, N.J, 1993.
- [AND 01] ANFRADE R., LISSER A., PLATEAU G., MACULAN N., “Simulation of the integer capacity planning under uncertain demand problem in telecommunication networks”, Proceedings EUROSIM 2001, DELFT, 2001.
-
[ARO 89] ARONSON J.E., “A survey on dynamic network flows”, Annals of Operations Research 20, p 1–66, 1989.
10.1007/BF02216922 Google Scholar
- [ARR 75] ARROW K.J., Choix Collectifs et Préférences Individuelles, Calmann-Levy, 1975.
- [ASH 98] ASHOK K., Estimation and prediction of time dependent origin-destination flows, PhD Thesis, MIT, 1998.
- [BALL 95] BALL M.O., MAGNANTI T.L., MONNA C.L., NEMHAUSER G.L., “Network routing”, Handbook in Operation Research Vol 8, North Holland Amsterdam, 1995.
- [BAR 95] BARAHONA F., “Network design using cut inequalities”, SIAM Journ on Optimization 6, p 822–837, 1995.
- [BARN 95] BARNHART C., HANE C.A., JOHNSON D.F., SIGISMONDI G., “A column generation and partitioning approach for multicommodity flow problems”, Telecommunication Systems 3, p 239–258, 1995.
- [BEN 00] BEN AMEUR W., “Constrained length connectivity and survivable networks”, Networks 36, 1, 2000.
- [BEN1 01] BEN AMEUR W., MICHEL N., GOURDIN E., LIAU B., “Routing strategies for IP networks” , Telektronik 2/3, p 145–158, 2001.
- [BENC 97] BENCHAKROUN A., FERLAND J., GASCON V., “Benders decomposition for network design problems with underlying tree structure”, Investigacion operativa 6, p 165–180, 1997.
- [BEND 01] BENDALI F., MAILFERT J., QUILLIOT A., “Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité”, Investigacion Operativa, 9, 30 pages, 2001.
-
[BEN 62] BENDERSZ J.F, “Partitionning procedures for solving mixed variable programming problems”, Num. Math. 4, p 238–252, 1962.
10.1007/BF01386316 Google Scholar
- [BER 57] BERGE C., Théorie des Jeux à n Personne”, Gauthier-Villars, Paris, Memorial Sciences Maths, 138, 1957.
- [BER 83] BERTSEKAS D.P, GAFNI E.M., “Projected Newton Methods and optimization of multicommodity flows”, IEEE Trans. Automat. Contr. AC-28, p 1090–1096, 1983.
-
[BIE 96] BIENSTOCK D., UNLUK O., “Capacited network design: polyhedral structure and computation”, INFORMS Journal of Computing 8, p 243–259, 1996.
10.1287/ijoc.8.3.243 Google Scholar
- [BIR 76] BIRD C.G., “On cost allocation on a spanning tree: a game theoretical approach”, Networks 6, p 335–350, 1976.
- [BOF 79] BOFFEY T., “Solving for optimal network problem”, EJOR 3, p 386–393, 1979.
- [BON 63] BONDAREVA O.N., “Applications of linear programming methods to the theory of cooperative games”, Problemy Kibernetica 10, p 119–139, 1963.
- [BRU 79] BRUYNEL G., “Computation of the nucleolus of a game by means of minimal balanced sets”, Operat. Res. Verfahren 34, p 35–51, 1979.
- [CAO 02] CAO X., SHEN H.X, MILITO R., Wirth P., “Internet pricing with a game theoretical approach: concepts and examples.”, IEEE/ACM Transactions on Networking 10, 2, p 208–215, 2002.
-
[CHAN 93] CHANG S.GT., GAVISH B., “Telecommunication network topological design and capacity expansion: formulations and algorithms”, Telecommunication Systems 1, –p 99131, (1993).
10.1007/BF02136157 Google Scholar
- [CHA 96] CHARDAIRE P., COSTA M.C., SUTTER A., “Solving the dynamic facility location problem”, Networks 28, p 117–124, (1996).
- [CHA 99] CHARDAIRE P., LUTTON J.L., SUTTTER A., “Upper and lower bounds for the two level simple plant location problem”, Annals of Operation Research 86, p 117–140, 1999.
- [CHAR 96] CHARDAIRE P., “Multihour design of computer backbone networks”, Telecommunication Systems 6, p 347–365, 1996.
- [CHI 94] CHIFFLET J., LISSER A., TOLLA P., “Interior point methods for multicommodity netflow problems”, Perquisa Operacional 15, p. 1, 1994.
- [CHI-1 94] CHIFFLET J., MAHEY P., REYNIER V., “Proximal decomposition for multi commodity flows problems with convex costs”, Telecom. Syst. 3, p 1–10, 1994.
- [CHO 94] CHOPRA S., RAO M., “The Steiner tree problem I: formulations, composition and extension of facets”, Math. Programming 64, p 209–229, 1994.
- [CHR 81] CHRISTOPHIDES L., WHITLOCK C.A., “Network synthesis with connectivity constraint: a survey”, Operations Research, p 705–723, 1981.
- [COC 93] COCCHI R., ZHENKER S., ESTRIN D., ZHANG L., “Pricing in computer networks: motivation, formulation, and example”, IEEE/ACM Transactions on Networking 1, p. 614–627, 1993.
- [CON 93] CONSTANTIN I., L'optimisation des fréquences d'un réseau de transport en commun, Rapport CRT 881 (PhD Thesis, Dir. M. Florian), University of Montreal, 1993.
- [COO 63] COOPER L., “Location allocation problems”, Operations Research 11, p 33–1343, 1963.
- [COR 98] CORDEAU J.P., TOTH P., VOGO D., “A survey of optimization models for train routing and scheduling”, Transportation Science 32, p 380–404, 1998.
- [CRA 00] CRAINIC T., GENDREAU M., FARVOLDEN J.M., “A simplex based tabu search method for capacitated network design”, INFORMS Journal on Computing 12, p 223–236, 2000.
- [CRA 01] CRAINIC T., FRANGIONI A., GENDRON B., “Bundle based relaxation methods for multicommodity capacitated fixed charge network design”, Discrete Applied Math. 112, p 73–99, 2001.
- [CUR 85] CURIEN N., “Cost allocation and pricing policy: the case of French telecommunications”; in Cost Allocation : Methods, Principles, Applications, Ed H.P. Young, Chapter 9, Elsevier Sciences, p 167–178, 1985.
- [DAF 82] DAFERMOS S., “The general multimodal network equilibrium problem with elastic demands”, Network 12, p 57–72, 1982.
- [DAG 77] DAGANZO C., “On the traffic assignment problem with flow dependent costs-II”, Transportation Research 11, p 439–441, 1977.
- [DAH 94] DAHL G., STOER M., “A polyhedral approach to multicommodity survivable network design”, Numerisch Mathematik 68, p 149–167, 1994.
- [DAS 89] DASKIN M.S., PANAYATOPOULOS M.D., “A lagrangean relaxation approach to assigning aircraft to routes in hub and spoke networks”, Transportation Science 23-2, p 91–99, 1989.
- [DEM 89] DEMBO R.M., MULVEY J.M., ZENIOS S.A, “Large scale non linear network models and their applications”, Operations Research 37-3, p 353–372, 1989.
- [DIO 79] DIONNE A., FLORIAN M., “Exact and approximate algorithms for optimal network design”, Networks 9, p 37–59, 1979.
- [DRE 88] DREYFUS C., SIARRY P., “La Méthode du Recuit Simulé”, IDEST PARIS, 1988.
-
[DRE 95] DREZNER S., Facility Location: A Survey of Applications and Methods, Springer-Verlag, 1995.
10.1007/978-1-4612-5355-6 Google Scholar
- [ECO 91] ECONOMIDES A., SILVESTER J., “Multiobjective routing in integrated service networks: a game theory approach”, Proc IEEE INFOCOM 91, p 1220–1227, 1991.
- [EIS 93] EISELT H.A., LAPORTE G., THISSE J.F., “Competitive location models: a framework and bibliography”, Transportation Sciences 27, p 44–54, 1993.
- [ENA 99] ENAMORADO J.C., Gomes T., Ramos A., “Multiarea regional interconnection planning under uncertainty”, In Proceedings 13 th Power Systems Computing Conference, 1999.
- [EKE 74] EKELAND I., La Théorie des Jeux et ses Applications à l'Economie Mathématique, Presses Universitaires de France, 1974.
- [FER 94] FERREIRA FILHO V.,, GALVAO J., “A survey of computer network design problems”, Investigacion Operativa 4, p 183–211, 1994.
- [FLO 84] FLORIAN M., “An introduction to network models used in transportation planning”, in M. Florian Ed, Transp. Plan. Models, North Holland, Amsterdam, p 137–152, 1984.
-
[FOR 62] FORD R.L., FULKERSON D.R., Flows in Networks, Princeton University Press, 1962.
10.1515/9781400875184 Google Scholar
- [GAL 83] GALLO G., “Lower planes for the network design problem”, Networks 13, p 411–426, 1983.
- [GAL 79] GALLO G., SODINI C., “Concave cost optimization on networks”, EJOR, p 23–9249, 1979.
- [GAR 98] GARCIA B.L, MAHEY P., LEBALNC L., “Iterative improvement methods for a multiperiod network design problem”, EJOR 110, p 150–165, 1998.
- [GA 79] GAREY M., JOHNSSON D., Computers and Intractability, W. Freeman and Co, 1979.
- [GAV 89] GAVISH B., NEUMAN I., “Routing in a network with unreliable components”, IEEE Trans on Communications 40, p 1248–1258, 1992.
-
[GAV 91] BAVISH B., “Topological design of telecommunication networks: local access design methods”, Annals of Operation Research 33, p 17–71, 1991.
10.1007/BF02061657 Google Scholar
- [GEN 93] GENDREAU M., LAPORTE G, MESA J.A., “Locating rapid transit lines: decision criteria and methodology”, Report CRT 907, University of Montreal, 1993.
-
[GEO 74] GEOFFRION A., “Lagrangean relaxation and its uses in integer programming”, Math. Prog. Study 2, p 82–114, 1974.
10.1007/BFb0120690 Google Scholar
-
[GEO 72] GEOFFRION A., “Generalized Benders decomposition”, Journal of Optimization Theory and Applications 10, p 237–260, 1972.
10.1007/BF00934810 Google Scholar
- [GIB 99] GIBBENS R.P., KELLY F.P., “Resource pricing and the evolution of congestion control”, Automatica 35, 12, p 1969–1985, 1999.
- [GIR 93] GIRARD A. LIAU B., “Dimensioning of adaptatively routed networks”, IEE/ACM Transactions on Networking 1–4, p 460–468, 1993.
-
[GLO 89] GLOVER F., “Tabu Search I”, ORSA Journal of Computing 1–3, p 190–206, 1989.
10.1287/ijoc.1.3.190 Google Scholar
- [GOF 97] GOFFIN J.L., GONDZION J., SARKISSIAN R., VIAL J.P.., “Solving non linear multicommodity flow problems by the analytic center cutting plane method”, Math. Prog. 76, p 131–154, 1997.
- [GOL 89] GOLDBERG A., TARJAN R., “Finding minimum cost circulation by cancelling negative cycles”, JACM 36 (4), p 873–886, 1989.
- [GOUV 95] GOUVEIA L., “Multicommodity flow models for spanning trees with hop constraints”, EJOR 95, p 178–190, 1995.
- [GRA 92] GRANOT D., GRANOT F., “On some network flow games”, Math. Operations Research 17, p 792–841, 1992.
- [GRA 84] GRANOT D., HUBERMAN G., “On the core and nucleolus of minimum spanning tree games”, Math. Programming 29, p 323–347, 1984.
- [GRO 92] GROTCHEL M., MONNA C.L, STOER M., “Computational results with a cutting plane algorithm for designing communication networks with low connectivity constraints”, Operations Research 40, p 309–330, 1992.
- [GRO 81] GROTSCHEL M., LOVACZ M., SCHRIJVER A., “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica 1, p 70–89, 1981.
-
[GRO 95] GROTCHEL M., MONNA C.L, STOER M., “Design of survivable networks”, In Network Models, p 617–672, North-holland, Amsterdam, 1995.
10.1016/S0927-0507(05)80127-6 Google Scholar
-
[GRO 90] GROTCHEL M., MONNA C.L, “Integer polyhedra arising from certain network design problems with connectivity constraints”
, SIAM Disc Math. 3, p 502–524, 1990.
10.1137/0403043 Google Scholar
-
[HOA 82] HOANG H., “Topological optimization of networks: a non linear mixed model employing generalized Benders decomposition”, IEEE Trans on Automatic Control AC-27, p 164–169, 1982.
10.1109/TAC.1982.1102873 Google Scholar
- [HOS 87] HOSSEIN P.A, BERTSEKAS D.P., TSENG P., “ Relaxation methods for network problems with convex arc costs”, S.I.A.M Journ. on Control and Optimization 5, 25, p 121–91243, 1987.
- [HWA 92). HWANG F.K, RICHARDS D.S, WINTER P., The Steiner Tree Problem, North Holland, 1992.
- [JAI 97] JAILLET P., SONG G., YU G., “Airline network design and hub location problems”, Location Science 4-3, p 195–212, 1997.
- [JAU 98] JAUMARD B., MARCOTTE O., MEYER M., “Mathematical models and exact methods for channel assignment in cellular networks”, In B. Sanso, P. Soriano, Eds, Telecommunications Network Planning, Kluwer, 1998.
- [JOC 66] JOCKSH H., “The shortest route problem with constraints”, Journal of Math. Analysis and Applications 14, p 191–197, 1966.
- [JOH 78] JOHNSON D., LENSTRA J., RINNOY KAN A., “The complexity of the Network Design Problem”, Networks 8, p 279–285, 1978.
- [JON 93] JONES K.L, LUSTIG I.J, FARVOLDEN J.M., POWEL W.B., “Multicommodity network flows : the impact of formulation on decomposition” , Math. Prog. 62, p 95–117, 1993.
- [KAL 82] KALAI E., ZEMEL E., “Totally balanced games and games of flows”, Math. Operat. Research 7, p 476–478, 1982.
- [KAT 96] KATZELA I., NAGHSINEH M., “Channel assignment schemes for cellular mobile telecommunication systems: a comprehensive survey”, IEEE Personnal Communications, p 10–30, 1996.
- [KEN 80] KENNINGTON J.L, HELGASON R.V, Algorithms for Network Programming, Wiley, 1980.
-
[KHU 72] KHUMALALA B.M., “Warehouse location problem efficient branch and bound algorithm”, Management Sciences B 18, p 718–731, 1972.
10.1287/mnsc.18.12.B718 Google Scholar
- [KLE 72] KLEINROCK L., Communications, Nets, Stochastic Messages Flow and Delay, Dover, 1972.
- [KLE75] KLEINROCK L., “Queuing Systems: Volume 1, Theory”, Wiley, 1975.
- [LA 99] LA R.J, ANANTHARAM V., “Network pricing using game theoretic approach”, In Proc 38 th IEEE Conf Decision and Control, vol. 4, p 4002–4007, 1999.
- [LAS 70] LASDON L.S., Optimization Theory for Large Systems, MacMillan, 1970.
- [LEB 73] LEBLANC L., Mathematical programming models for large scale network equilibrium and network design problems, PhD thesis, NorthWestern University Evanston, 1973.
- [LEB 75] LEBALNC L., “An algorithm for discrete network design”, Trans. Sci. 9, p 28–3287, 1975.
- [LEB 81] LEBLANC L., FARHANGIAN K., “Efficient algorithms for solving elastic demand traffic assignment problems and mode split assignment problems”, Transp. Sci. 15, p 30–6317, 1981.
- [LED 93] LEDERER P.J., “A competitive network design problem with pricing”, Transportation Sciences 27, p 25–38, 1993.
- [LEB 99] LEBLANC L., CHIFFLET J., MAHEY P., “Packet routing in telecommunication networks with path and flow restrictions”, INFORMS Journal of Computing 11, 2, 1999.
- [MAC 91] MACGREGOR J., WINTER P., “Topological Network Design”, Annals of Operation Research 33, 1991.
- [MAG 78] MAGNANTI T.L., GOLDEN B.L., “Transportation planning: network models and their implementation”, in A.C. HAX ed:., Studies in Operation Management, p 465–518, 1978.
- [MAG 93] MAGNANTI T.L., MIRCHANDANI P., “Shortest paths, single origin-destination network design, and associated polyhedra”, Networks 23, 2, p 103–121, 1993.
- [MAH 98] MAHEY P., OUOUROU. A., LEBLANC L., CHIFFLET J., “A new proximal decomposition algorithm for routing in telecommunication networks” , Networks 31, p 227–238, 1998.
- [MAH 01] MAHEY P., BENSHAKROUN A., BOYER F, “Capacity and flow assignment of data networks by generalized Benders decomposition” , Journal of Global Optimization 20, p 173–193, 2001.
- [MAH 94] MAHJOUB A.R., “Two edge connected spanning subgraphs and polyhedra”, Mathematical Programming 64, p 199–208, 1994.
- [MAH 05] MAHJOUB A.R., “Méthodes polyédrales”, V.Th. Paschos, Ed., Optimisation Combinatoire : Concepts Fondamentaux, chapter 8, Hermes, Paris, 2005.
- [MAK 95] MACKNIGHT L.W., BAILEY J.P., Internet Economics, MIT PRESS, Cambridge, 1995.
- [MAU 99] MAUBLANC J., PEYRTON D., QUILLIOT A., “Multiple routing strategies in a labelled graph”, Investigacion Operativa 7, 3, p 101–133, 2001.
- [MINI 78] MINIEKA E., Optimization Algorithms for Networks and Graphs, Marcel Dekker Inc., 1978.
-
[MIN 87] MINOUX, M., “Network synthesis and dynamic network optimization”; InMartello S., Laporte G., Minoux M., Ribeiro C., Eds., Surveys in Combinatorial Optimization, Chapter 9, p 283–324, North Holland, 1987.
10.1016/S0304-0208(08)73239-0 Google Scholar
- [MIN 89] MINOUX M., “Network synthesis and optimum network design problems: models, solution methods and application”, Networks 19, p 313–360, 1989.
-
[MIN 81] MINOUX M., “Optimum synthesis of a network with non simultaneous multicommodity flow requirements”, P. Hansen ed., Studies on graphs and Discrete Programming, Annals of Disc. Math. 11, North Holland, p 269–277, 1981.
10.1016/S0304-0208(08)73470-4 Google Scholar
- [MIN 75] MINOUX M., “Plus courts chemins avec contraintes”, Annales des Télécommunications 30, p 383–394, 1975.
- [NAG 88] NAGAMOCHI H., Studies on multicommodity flows in directed networks, Eng. Doc. Thesis, Kyoto University, 1988.
- [NAS 51] NASH J., “Non cooperative games”, Ann. of Math. 54, p 286–295, 1951.
- [ORD 93] ORDA A., ROM R., SHIMKIN N., “Competitive routing in multiuser communication networks”, IEEE/ACM Trans Networking 1, p 510–521, 1993.
- [OUO 00] OUOROU A., MAHEY P., VIAL J.P., “A survey of algorithms for convex multicommodity flow problems”, Management Science 46, 1, p 126–147, 2000.
- [OUO1 00] OUOROU A., “A minimum mean cycle cancelling method for non linear multicommodity flow problems”, EJOR 121, p 532–548, 2000.
- [OWE 82] OWEN G., Game Theory, Academic Press, 1982.
- [PAR 98] PARDALOS P.M., DU D.Z., “Network design: connectivity and facility location”, DIMACS Series 40, N.Y, American Math. Society, 1998.
- [PEA 86] PEARL J., Heuristics, Prentice Hall, 1986.
-
[PEA 74] PEARMAN A.D., “Heuristic approaches to network optimization”, Optimization 1, p 37–49, 1974.
10.1080/03052157408960575 Google Scholar
- [QUI 85] QUILLIOT A., “A retraction problem in graph theory”, Disc. Math. 54, p 61–71, 1985.
- [REB 00] REBAI R., Optimisation de réseaux de télécommunications avec sécurisation, Thesis, Paris-Dauphiine, 2000.
- [SCH 77] SCHWARTZ M., Computer Communication Network Design and Analysis, Prentice Hall, 1977.
-
[SHA 71] SHAPLEY L.S., “Cores of convex games”, Int. J .Game Theory 1, p 11–26, 1971.
10.1007/BF01753431 Google Scholar
- [SMA 74] SMART D.R., “Fixed point theorems”, Cambridge Tracts in Mathematics 66, 1974.
- [SPI 85] SPINGARN J.E., “Applications of the method of partial inverse to convex programming decomposition”, Math. Programming 32, p 199–223, 1985.
- [STE 74] STEENBRINK P.A., Optimization of Transport Networks, Wiley, 1974.
- [STE 69] STEIGLITZ K., WEINER P., KLEITMAN D.J., “The design of minimum cost survivable networks”, IEEE Trans and Circuits Theory 16, p 455–460, 1969.
- [TAM 91] TAMIR A., “On the core of network synthesis games”, Math. Programming 50, p 123–135, 1991.
- [TSE 90] TSENG P., “Dual ascent methods for problems with strictly convex costs and linear constraints : a unified approach”, SIAM Journal on Control and Optimization 28, p 214–242, 1990.
- [WON 80] WONG R.T., “Worst case analysis of network design problem heuristics”, SIAM J. Alg. Disc. Meth. 1, p 51–63, 1980.
-
[YAG 73] YAGED B., “Minimum cost routing for dynamic network models”, Networks 3, p 315–331, 1973.
10.1002/net.3230030302 Google Scholar
- [YAM 96] YAMAOKA K., SAKAI Y., “A packet routing method based on game theory”, Trans Inst Electronics, Information and Communication Engineers B-I, J79B-I, p 73–79, 1996.
