{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T09:51:20Z","timestamp":1771235480209,"version":"3.50.1"},"reference-count":120,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6372,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1989,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper is intended as a survey in the area of network synthesis and optimum network design, which, in view of the importance and variety of the underlying applications, has attraced, since the early 1960s, much interest in the Operations Research community. Indeed, if the first models were studied in connection with telecommunication networks, the range of applications kept on getting broader and broader, including transportation networks, computer and teleprocessing networks, energy transport systems, water distribution networks, etc. However, beyond the apparent diversity of practical situations involved, most of these applications can be accounted for (modulo possibly a few minor adaptations), by a rather limited number of basic models. One of the main purposes of this paper is to provide the reader with a relevant classification of the area which will help him identify the fundamental structure of the problem (if any) he has to cope with, and relate it to already published work. In order to obtain a fairly good coverage of the matter, we have thus been led to identify three basic models aroung which the whole paper is organized: a general model using minimum cost multicommodity flows (Section 2); models in terms of tree\u2010like networks (Section 3); models using nonsmultaneous single\u2010commodity or multicommodity flows (Section 4). In each bcase the most important variants of the basic models have been surveyed with the purpose of providing as much information as possible concerning (a) the various contexts of applications from which the problem arose; (b) the main computational methods proposed in the literature for solving it, with emphasis on those techniques which appear at present, to be most efficient or promising.<\/jats:p>","DOI":"10.1002\/net.3230190305","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T02:48:39Z","timestamp":1178938119000},"page":"313-360","source":"Crossref","is-referenced-by-count":307,"title":["Networks synthesis and optimum network design problems: Models, solution methods and applications"],"prefix":"10.1002","volume":"19","author":[{"given":"M.","family":"Minoux","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100207"},{"key":"e_1_2_1_3_2","unstructured":"D.ArdittiandM.Minoux Un algorithme de determination de partition utilisant la dualit\u00e9 lagrangienne. Actes regroup\u00e9s des journ\u00e9es de classification de Toulouse (mai1980) et nancy (Juin 1981). I.C. Lerman Ed."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080107"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800080104"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140112"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386316"},{"key":"e_1_2_1_8_2","unstructured":"O.BildeandJ.Krarup Bestemmels af optimal beliggenhed of Produktionssteder. Research report IMSOR Danmarks Tekniske Hojskole (1967)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.7.1.49"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(79)90118-8"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1068\/a050519"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"R. R.BoorstynandH.Frank Large scale network topological optimization.IEEE Trans. Comm.COM\u201025(1977)29\u201347.","DOI":"10.1109\/TCOM.1977.1093708"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/9.3.263"},{"key":"e_1_2_1_14_2","first-page":"65","article-title":"Tree searching methods with an application to a network design problem","volume":"1","author":"Burstall R. M.","year":"1967","journal-title":"Machine Intelligence"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030204"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1972.223452"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580236"},{"key":"e_1_2_1_18_2","unstructured":"A.ClausandN.Maculan Une nouvelle formulation du probl\u00e8me de Steiner sur un graphe. Pr\u00e9publication #280 Centre de Recherche sur les Transports. Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.20.1.94"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(79)90003-1"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800160306"},{"key":"e_1_2_1_22_2","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow on a network with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","journal-title":"Soviet math Dokl."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090104"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.5.259"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"D.EliasandM. J.Ferguson Topological design of multipoint teleprocessing networks.IEEE Trans. Comm. COM\u201022(1974)1753\u20131762.","DOI":"10.1109\/TCOM.1974.1092122"},{"issue":"50","key":"e_1_2_1_27_2","first-page":"4","article-title":"La loi des volumes \u00e9conomiques appliqu\u00e9e aud T\u00e9l\u00e9communications","volume":"1","author":"Ellis L. W.","year":"1975","journal-title":"Rev. Telecom."},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.6.992"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.53.0142"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.27.1.1"},{"key":"e_1_2_1_31_2","first-page":"219","volume-title":"Numerical Methods for Constrainted Optimization","author":"Fletcher R.","year":"1974"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.3.184"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1972.8910"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1972.8551"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130309"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(79)90144-9"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(80)90109-5"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.5.1112"},{"key":"e_1_2_1_41_2","volume-title":"Computers and Intractability: A guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120402"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322367"},{"key":"e_1_2_1_44_2","unstructured":"B.Gavish Augmented lagrangean based algorithms for centralized network design. Working paper QM 8321 The Graduate School of Management The University of Rochester NY14627(1984)."},{"key":"e_1_2_1_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120690"},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/1013001"},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.822"},{"key":"e_1_2_1_48_2","doi-asserted-by":"crossref","unstructured":"M.GerlaandL.Kleinrock On the topological design of distributed computer networks.IEEE Trans. Comm.COM\u201025(1977)48\u201360.","DOI":"10.1109\/TCOM.1977.1093709"},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.1.156"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/0110020"},{"key":"e_1_2_1_52_2","doi-asserted-by":"publisher","DOI":"10.1137\/0112029"},{"key":"e_1_2_1_53_2","volume-title":"Graphes et algorithmes","author":"Gondran M.","year":"1979"},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.6.1529"},{"key":"e_1_2_1_55_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"e_1_2_1_56_2","unstructured":"P.Hansen The optimum rented lines network problem. Symposium \u201cOperations Research in Telecommunications\u201d held at Rutgers University Rutgers Center for Operations Research November 30 1984."},{"key":"e_1_2_1_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.5.488"},{"key":"e_1_2_1_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1982.1102873"},{"key":"e_1_2_1_60_2","doi-asserted-by":"publisher","DOI":"10.1137\/0203015"},{"key":"e_1_2_1_61_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080402"},{"key":"e_1_2_1_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1976.1093334"},{"key":"e_1_2_1_63_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_2_1_64_2","first-page":"434","article-title":"Determining the maximal flow in a network by the method of perflows","volume":"15","author":"Karzanov A. V.","year":"1974","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_65_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.2.209"},{"key":"e_1_2_1_66_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040403"},{"key":"e_1_2_1_67_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130211"},{"key":"e_1_2_1_68_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094601"},{"key":"e_1_2_1_69_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.12.B718"},{"key":"e_1_2_1_70_2","unstructured":"H.Kobayashi Communication network design and control algorithms\u2014a survey. Research Report RC 9233 IBM Thomas J. Watson Research Centre (1982)."},{"key":"e_1_2_1_71_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.699"},{"key":"e_1_2_1_72_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.9.3.183"},{"key":"e_1_2_1_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(81)90134-6"},{"key":"e_1_2_1_74_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.11.6.972"},{"key":"e_1_2_1_75_2","first-page":"89","article-title":"Combinatorial programming, statistical optimization and the optimal transportation network problem","author":"Los M.","year":"1980","journal-title":"Trans. Res."},{"key":"e_1_2_1_76_2","volume-title":"Tailoring Benders decomposition for network design","author":"Magnanti T. L.","year":"1983"},{"key":"e_1_2_1_77_2","unstructured":"T. L.MagnantiandR. T.Wong Accelerating Benders decomposition for network design. Discussion Paper C.O.R.E. Belgium (1977)."},{"key":"e_1_2_1_78_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"e_1_2_1_79_2","unstructured":"T. L.MagnantiandR. T.Wong A dual ascent approach to fixed charge network design problems. To appear."},{"key":"e_1_2_1_80_2","doi-asserted-by":"publisher","DOI":"10.1080\/00207177208932320"},{"key":"e_1_2_1_81_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90016-9"},{"key":"e_1_2_1_82_2","unstructured":"P.Marcotte An analysis of heuristics for the network design problem. Publication #200 Centre de recherche sur les transports Universit\u00e9 de Montr\u00e9al (1982)."},{"key":"e_1_2_1_83_2","first-page":"419","volume-title":"Optimization Techniques","author":"Minoux M.","year":"1976"},{"key":"e_1_2_1_84_2","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF02997589","article-title":"Multiflots de cut minimal avec fonctions de cot concaves","volume":"31","author":"Minoux M.","year":"1976","journal-title":"Annales des T\u00e9l\u00e9communications."},{"key":"e_1_2_1_85_2","first-page":"59","article-title":"Algorithmes gloutons et algorithmes gloutons acc\u00e9l\u00e9r\u00e9s pour la r\u00e9solution des grands probl\u00e9mes combinatoires","volume":"1","author":"Minoux M.","year":"1977","journal-title":"Bull. Dir. Et. Rech. EDF, S\u00e9rie C"},{"key":"e_1_2_1_86_2","first-page":"234","volume-title":"Accelerated greedy algorithms for maximizing submodular set functions","author":"Minoux M.","year":"1977"},{"key":"e_1_2_1_87_2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1007\/BF02995852","article-title":"Plantification \u00e8 court et \u00e8 moyen terme d'un r\u00e9seau de T\u00e9l\u00e9communications","volume":"29","author":"Minoux M.","year":"1974","journal-title":"Annales des T\u00e9l\u00e9communications"},{"key":"e_1_2_1_88_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73470-4"},{"key":"e_1_2_1_89_2","volume-title":"Programmation Math\u00e9matique: th\u00e9orie et algorithmes","author":"Minoux M.","year":"1983"},{"key":"e_1_2_1_90_2","unstructured":"M.Minoux Localisation optimale de concentrateurs dans un reseau t\u00e9l\u00e9informatique. Unpublished report May (1984)."},{"key":"e_1_2_1_91_2","first-page":"271","volume-title":"Mathematical Programming","author":"Minoux M.","year":"1984"},{"key":"e_1_2_1_92_2","first-page":"283","article-title":"Network synthesis and dynamic network optimization\u201d in Surveys in Combinational Optimization","volume":"31","author":"Minoux M.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_93_2","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF02999753","article-title":"Synth\u00e8se optimale d'un r\u00e9seau de T\u00e9l\u00e9communications avec contraintes de s\u00e9curit\u00e9","volume":"36","author":"Minoux M.","year":"1981","journal-title":"Annales des T\u00e9l\u00e9communications"},{"key":"e_1_2_1_94_2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1051\/ro\/1981150201851","article-title":"Subgradient optimization and large scale programming: an application to network synthesis wiht security constraints","volume":"15","author":"Minoux M.","year":"1981","journal-title":"RAIRO"},{"key":"e_1_2_1_95_2","unstructured":"M.MinouxandJ. J.Strodiot Un algorithme exact pur les probl\u00e8mes de multiflots de cot minimum avec fonctions de cot concaves. Unpublished report\u2014CNET (1982)."},{"key":"e_1_2_1_96_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.25.4.329"},{"key":"e_1_2_1_97_2","unstructured":"J. D.Murchland A fixed matrix for all shortest distances in a directed graph and for the inverse problem. Doctoral Thesis University of Karlsruhe (1970)."},{"key":"e_1_2_1_98_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080306"},{"key":"e_1_2_1_99_2","doi-asserted-by":"publisher","DOI":"10.1080\/03052157408960575"},{"key":"e_1_2_1_100_2","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(79)90008-0"},{"key":"e_1_2_1_101_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1957.tb01515.x"},{"key":"e_1_2_1_102_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(68)90105-6"},{"key":"e_1_2_1_103_2","volume-title":"Computer Communications Network Design and Analysis","author":"Schwartz M.","year":"1977"},{"key":"e_1_2_1_104_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(69)90152-X"},{"key":"e_1_2_1_105_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.1.85"},{"key":"e_1_2_1_106_2","first-page":"218","article-title":"Selecting an optimal traffic network","volume":"2","author":"Stairs S.","year":"1968","journal-title":"J. Transport Econ. Policy"},{"key":"e_1_2_1_107_2","volume-title":"Optimization of Transport Networks","author":"Steenbrink P. A.","year":"1974"},{"key":"e_1_2_1_108_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800170209"},{"key":"e_1_2_1_109_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1978.1675159"},{"key":"e_1_2_1_110_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90076-2"},{"key":"e_1_2_1_111_2","first-page":"32","article-title":"Concave programming under linear constraints","volume":"159","author":"Tuy H.","year":"1964","journal-title":"Dokl. Akad. Nauk. SSR"},{"key":"e_1_2_1_111_3","first-page":"1437","volume":"5","year":"1964","journal-title":"Translated Soviet Math."},{"key":"e_1_2_1_112_2","unstructured":"H.Tuy Global maximization of a convex function over a closed convex not necessarily bounded set. Unpublished Report.1982."},{"key":"e_1_2_1_113_2","unstructured":"L.Van SickleandK. M.Chandy Computational complexity of network algorithms.IFIP Congress Proceedings (1977)235\u2013239."},{"key":"e_1_2_1_114_2","doi-asserted-by":"publisher","DOI":"10.1137\/0601008"},{"key":"e_1_2_1_115_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"},{"key":"e_1_2_1_116_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010205"},{"key":"e_1_2_1_117_2","first-page":"193","volume":"3","author":"Yaged B.","year":"1973","journal-title":"Minimum cost routing for dynamic network models"},{"key":"e_1_2_1_118_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230030404"},{"key":"e_1_2_1_119_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040104"},{"key":"e_1_2_1_120_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.7.429"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230190305","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230190305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T15:17:23Z","timestamp":1697987843000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230190305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,5]]},"references-count":120,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1989,5]]}},"alternative-id":["10.1002\/net.3230190305"],"URL":"https:\/\/doi.org\/10.1002\/net.3230190305","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,5]]}}}