Flots entiers et multiflots fractionnaires couplés par une contrainte de capacité
Alain Quilliot; Fatiha Bendali; Jean Mailfert
RAIRO - Operations Research - Recherche Opérationnelle (2005)
- Volume: 39, Issue: 3, page 185-224
- ISSN: 0399-0559
Access Full Article
topAbstract
topHow to cite
topReferences
top- [1] R.K. Ahuja, J.B. Orlin and D. Sharma, Multiexchance neighbourhood structures for the capacitated minimum spanning tree problem. Math Programming 91 (2001) 71–97. Zbl1051.90019
- [2] R.K. Ahuja, T.L. Magnanti, J.B. Orlin and M.R. Reddy, Applications of network optimization. Chapter 1 of Network Models, Handbook of Operation Research and Management Science 7 (1995)1–83. Zbl0833.90116
- [3] R.V. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows Theory, Algorithms and Applications. Prentice hall, Englewood Cliffs, N.J. (1993). Zbl1201.90001MR1205775
- [4] J.E. Aronson, A survey on dynamic network flows. Ann. Oper. Res. 20 (1989) 1–66. Zbl0704.90028
- [5] A. Assad, Multicommodity networks flows a survey. Networks 8 (1978) 37–91. Zbl0381.90040
- [6] A. Balakrishnan, T. Magnanti and P. Mirchandani, Designing hierarchical survivable networks. Oper. Res. 46 (1998) 116–130. Zbl0987.90517
- [7] A. Balakrishnan, T. Magnanti and P. Mirchandani, A dual based algorithm for multi level network design. Manage. Sci. 40 (1994) 567–580. Zbl0826.90117
- [8] M. Balinski, Fixed cost transportation problems. Nov. Res. Log. Quart 8 (1961) 41–54. Zbl0106.34801
- [9] F. Barahona, Network design using cut inequalities. SIAM J. Optim. 6 (1995) 822–837. Zbl0856.90112
- [10] W. Ben Ameur, Constrained length connectivity and survivable networks. Networks 36 (2000) 1. Zbl0971.90010MR1772469
- [11] A. Benchakroun, J. Ferland and V. Gascon, Benders decomposition for network design problems with underlying tree structure. Investigacion operativa 6 (1997) 165–180.
- [12] J.F. Benders, Partitionning procedures for solving mixed variable programming problems. Num. Math. 4 (1962) 238–252. Zbl0109.38302
- [13] D. Bertsimas and S. Stock Patterson, The air traffic flow problem with en route capacities. Oper. Res. 46-3 (1998) 406–422. Zbl0996.90010
- [14] D. Bienstock and O. Unluk, Capacited network design polyedral structure and computation. Inform. J. Comput. 8 (1996) 243–259. Zbl0871.90031
- [15] T. Boffey and A. Hinxman, Solving for optimal network problem. EJOR 3 (1979) 386–393. Zbl0424.90074
- [16] A. Caminada, J.K. Hao, J.L. Lutton and V. Martin, L’optimisation des réseaux de télécommunications. Recherche Opérationnelle et Réseaux : Méthodes d’Analyse Spatiale. Collection IGAT, Hermes, Chap. 7 (2002) 191–236.
- [17] S.G. Chang and B. Gavish, Telecommunication network topological design and capacity expansion formulations and algorithms. Telecom. Syst. 1 (1993) 99–131.
- [18] P. Chardaire, M.C. Costa and A. Sutter, Solving the dynamic facility location problem. Networks 28 (1996) 117–124. Zbl0864.90073
- [19] J. Chifflet, A. Lisser and P. Tolla, Interior point methods for multicommodity netflow problems. Perquisa Operacional 15 (1994) 1.
- [20] S. Chopra and M. Rao, The Steiner tree problem I: formulations, composition and extension of facets. Math Programming 64 (1994) 209–229. Zbl0821.90124
- [21] N. Christophides, C.A. Whitlock, Network synthesis with connectivity constraint a survey. Oper. Res. (1981) 705–723. Zbl0473.90036
- [22] J.P. Cordeau, P. Toth and D. Vigo, A survey of optimization models for train routing and scheduling. Transportation Science 32 (1998) 380–404. Zbl0987.90507
- [23] T. Crainic, M. Gendreau and J.M. Farvolden, A simplex based tabu search method for capacitated network design. Inform. J. Comput. 12 (2000) 223–236. Zbl1040.90506
- [24] T. Crainic and J.M. Rousseau, Multicommodity, multimode freight transportation a general modeling and algorithmic framework for the service network design problem. Transport Research B 20 (1988) 290–297.
- [25] T. Crainic, A. Frangioni and B. Gendron, Bundle based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Appl. Math. 112 (2001) 73–99. Zbl1026.90010
- [26] G. Dahl and M. Stoer, A polyedral approach to multicommodity survivable network design. Numer. Math. 68 (1994) 149–167. Zbl0809.65068
- [27] P. Dejax and T. Crainic, A review of empty flow and fleet management models in freight transportation. Transportation Science 21 (1987) 227–247.
- [28] D. De Wolf and Y. Smeers, Optimal dimensionning of pipe networks with application to gas transmission networks. Oper. Res. 44-4 (1996) 596–608. Zbl0865.90042
- [29] A. Dionne and M. Florian, Exact and approximate algorithms for optimal network design. Networks 9 (1979) 37–59. Zbl0397.94024
- [30] Z. Drezner and T. Drezner, Applied location theory models, in Modern Methods for Business Research, edited by Lawrence Erlbaum Mahwa, N.J. (1998) 79–120.
- [31] H.A. Eiselt, G. Laporte and J.F. Thisse, Competitive location models a framework and bibliography. Transportation Sciences 27 (1993) 44–54. Zbl0767.90006
- [32] V. Ferreira Filho and J. Galvao, A survey of computer network design problems. Investigacion Operativa 4 (1994) 183–211.
- [33] M. Florian, An introduction to network models used in transportation planning, in Transp. Plann. Models, edited by M. Florian, North Holland, Amsterdam (1984) 137–152. Zbl0591.90092
- [34] J.M. Forvalden, W.B. Powell and I. Lustig, A primal partitionning solution for the arc chain formulation of a multicommodity network flow problem. Oper. Res. 41 (1993) 669–693. Zbl0782.90032
- [35] G. Gallo, Lower planes for the network design problem. Networks 13 (1983) 411–426. Zbl0523.90087
- [36] B. Gavish, Topological design of telecommunication networks local access design methods. Ann. Oper. Res. 33 (1991) 17–71. Zbl0736.90030
- [37] A. Geoffrion, Lagrangean relaxation and its uses in integer programming. Math. Prog. Study 2 (1974) 82–114. Zbl0395.90056
- [38] A. Geoffrion, Generalized Benders decomposition. J. Optim. Theory Appl. 10 (1972) 237–260. Zbl0229.90024
- [39] A. Girard and B. Liau, Dimensioning of adaptatively routed networks. IEE/ACM Trans. Networking 1-4 (1993) 460–468.
- [40] A. Golberg and R. Tarjan, Finding minimum cost circulation by cancelling negative cycles, JACM 36 (1989) 873–886. Zbl0697.68063
- [41] H. Hoang, Topological optimization of networks a non linear mixed model employing generalized Benders decomposition. IEEE Trans. Automat. Control. AC-27 (1982) 164–169. Zbl0472.90068
- [42] P.A. Hossein, D.P. Bertsekas and P. Tseng, Relaxation methods for network problems with convex arc costs. SIAM J. Control Optim. 5 (1987) 1219–1243. Zbl0641.90036
- [43] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. North Holland (1992). Zbl0774.05001MR1192785
- [44] P. Jaillet, G. Song and G. Yu, Airline network design and hub location problems. Location Science 4 (1997) 195–212. Zbl0929.90048
- [45] D. Johnson, J. Lenstra, A. RInnoy-Khan, The complexity of the Network Design Problem. Networks 8 (1978) 279–285. Zbl0395.94048
- [46] K.L. Jones, I.J. Lustig, J.M. Farvolden and W.B. Powel, Multicommodity network flows the impact of formulation on decomposition. Math. Programming 62 (1993) 95–117. Zbl0802.90039
- [47] J.L. Kennington and R.V. Helgason, Algorithms for network programming. Wiley N.Y. (1980). Zbl0502.90056MR581251
- [48] B.M. Khumalala, Warehouse location problem efficient branch and bound algorithm. Manage. Sciences B 18 (1972) 718–731. Zbl0238.90048
- [49] J.G. Klincewicz and M.B. Rosenwein, Planning and consolidating shipments from a warehouse. J. Operat. Res. Soc. 48 (1997) 241–246. Zbl0890.90058
- [50] L.J. Leblanc, An algorithm for discrete network design. Trans. Sci. 9 (1975) 283–287.
- [51] P.J. Lederer and R.S. Nambimadom, Airline network design. Oper. Res. 46-6 (1998) 785–804. Zbl0987.90509
- [52] J. Mac Gregor Smith and P. Winter, Topological Network Design. Ann. Oper. Res. 33 (1991). MR1140997
- [53] T. Magnanti, Combinatorial optimization and vehicle fleet planning perspectives and prospects. Networks 11 (1981) 179–214.
- [54] T. Magnanti and R.T. Wong, Network design and transportation planning models and algorithms. Trans. Sci. 18 (1984) 1–5.
- [55] P. Mahey, A. Benchakroun and F. Boyer, Capacity and flow assignment of data networks by generalized Benders decomposition. J. Global Optim. 20 (2001) 173–193. Zbl1002.90082
- [56] A. Marin and J. Salmeron, Tactical design of rail freight networks part 1- exact and heuristic methods. EJOR 90 (1996) 26–44. Zbl0916.90096
- [57] M. Minoux, Network synthesis and optimum network design problems models, solution methods and application. Networks 19 (1989) 313–360. Zbl0666.90032
- [58] M. Minoux, Optimum synthesis of a network with non simultaneous multicommodity flow requirements, Studies on graphs and Discrete Programming, Annals of Disc. Math., edited by P. Hansen, North Holland 11 (1981) 269–277. Zbl0469.90080
- [59] P.B. Mirchandani and L.R. Francis, Discrete Location Theory. John Wiley Eds, N.Y. (1990). Zbl0718.00021MR1066256
- [60] I. Norenkov, Y. Yevstifeyev and V. Manichev, A method for an accelerated analysis of multiperiod electronic circuits. Telecom Radio Engin. 42 (1987) 123–126.
- [61] A. Ouorou, P. Mahey and J.P. Vial, A survey of algorithms for convex multicommodity flow problems. Manage. Science 46 (2000) 126–147. Zbl1231.90110
- [62] P.M. Pardalos and D.Z. Du, Network design connectivity and facility location. DIMACS Series 40, N.Y., American Math Society (1998). MR1612993
- [63] R. Rebai, Optimisation de réseaux de télécommunications avec sécurisation. Thèse Paris-Dauphine (2000).
- [64] T. Scott and E. Read, Modelling hydroreservoir operation in a deregulated electricity market. ITOR 3 (1996) 243–253. Zbl0874.90122
- [65] P.A. Steenbrink, Optimization of transport networks. Wiley, N.Y. (1974).
- [66] P. Tseng, Dual Ascent methods for problems with strictly convex costs and linear constraints a unified approach. SIAM J. Control Optim. 28 (1990) 214–242. Zbl0692.49025
- [67] R. Vijay, A. Kanda and P. Vrat, Multiperiod capacity expansion of road networks formulation and algorithms. Oper. Res. 30 (1993) 117–140. Zbl0795.90020
- [68] R.T. Wong, Worst case analysis of network design problem heuristics. SIAM J. Alg. Disc. Meth. 1 (1980) 51–63. Zbl0498.90032