{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T14:31:37Z","timestamp":1751985097391,"version":"3.32.0"},"reference-count":32,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Although there is an extensive literature dealing with network design, little attention has been devoted to networks with complicated node costs. Although node costs, depending linearly on the total passing flow, can be easily embedded into the more usual framework of networks with link costs, when the node costs are, for instance, a stepwise function of the facilities installed into the nodes, this is no longer possible. This feature seems to be crucial in modern telecommunications networks, but has also applications in other fields, where a limited set of technologies is available with discrete values of capacities and costs. In our specific application, we propose a mathematical programming model that explicitly accounts for node costs that are stepwise with nonlinear increments. Two families of valid inequalities are then introduced, one of which is an extension of those presented in a previous work by Stoer and Dahl for multifacility network models. As the separation problem for these inequalities is difficult, we develop a heuristic separation procedure. We devise a branch\u2010and\u2010cut method and test it on a set of real\u2010world instances found in the network design literature. This new method proves to be efficient when compared to a commercial general purpose MIP algorithm. \u00a9 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 90\u201399 2007<\/jats:p>","DOI":"10.1002\/net.20144","type":"journal-article","created":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T21:29:51Z","timestamp":1160602191000},"page":"90-99","source":"Crossref","is-referenced-by-count":16,"title":["Multicommodity network design with discrete node costs"],"prefix":"10.1002","volume":"49","author":[{"given":"P.","family":"Belotti","sequence":"first","affiliation":[]},{"given":"F.","family":"Malucelli","sequence":"additional","affiliation":[]},{"given":"L.","family":"Brunetta","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.50.2.333.423"},{"key":"e_1_2_1_3_2","unstructured":"D.Alevras M.Gr\u00f6tschel R.Wess\u00e4ly A network dimensioning tool ZIB Preprint SC 96\u201049 Berlin."},{"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.1007\/s101070100284"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.2.243.12223"},{"key":"e_1_2_1_7_2","unstructured":"E.Balas C.C.de Souza The Vertex Separation Problem: Polyhedral investigations Research report MSRR\u2010670 GSIA Carnegie Mellon University Pittsburgh 2003."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"Q1","DOI":"10.1109\/COMST.1999.5340507","article-title":"Regular multihop logical topologies for lightwave networks","volume":"2","author":"Banerjee S.","year":"1999","journal-title":"IEEE Commun Surveys"},{"key":"e_1_2_1_9_2","unstructured":"P.Belotti L.Brunetta F.Malucelli Multicommodity network design with discrete node costs Internal report 2005.30 DEI Politecnico di Milano."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000211"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.243"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.49.9.1268.16570"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1090\/dimacs\/005\/07","article-title":"The optimal multiterminal cut problem","volume":"5","author":"Cunningham W.H.","year":"1991","journal-title":"DIMACS Series in Discrete Math Theor Comput Sci"},{"key":"e_1_2_1_14_2","unstructured":"J.Frodsham A.Solheim Next generation backbone network metrics Proceedings of National Fiber Optic Engineers Conference Baltimore MD July 8\u201312 2001."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(99)00020-6"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-5087-7_1"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050077"},{"key":"e_1_2_1_18_2","unstructured":"Ilog Cplex Division Cplex Optimization Package.http:\/\/www.cplex.com."},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"J.P.Jue D.Datta B.Mukherjee A new node architecture for scalable WDM Optical networks Proceedings IEEE ICC '99 Vancouver BC vol. 3 June1999 pp.1714\u20131718.","DOI":"10.1109\/ICC.1999.765532"},{"key":"e_1_2_1_20_2","unstructured":"A.Kanevsky \u201cOn the number of minimum size separating vertex sets in a graph and how to find all of them \u201d Proc. SODA 1990 pp.411\u2013421."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00059-2"},{"key":"e_1_2_1_22_2","unstructured":"J.L.Kennington V.S.S.Nair G.Spiride Optimal spare capacity assignment for path restorable mesh networks: Cuts decomposition and an empirical analysis Technical report 98\u2010CSE\u201011 Southern Methodist University Dallas TX 1998."},{"key":"e_1_2_1_23_2","unstructured":"A.Kr\u00f6ller R.Wess\u00e4ly Integrated optimization of hardware configuration and capacity dimensioning in SDH and opaque WDM networks Proceedings INOC 2003 Paris\u2010Evry 2003."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.1.142"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230205"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014554606793"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1971.1083312"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0038-2"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016671128891"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)83809-1"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050054"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/35.910602"},{"key":"e_1_2_1_33_2","unstructured":"D.Yuan \u201cAn annotated bibliography in communication network design and routing \u201d Optimization models and methods for communication network design and routing PhD dissertation no. 682 (2001) Institute of Technology Link\u00f6pings Universitet Link\u00f6ping Sweden."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20144","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T11:35:28Z","timestamp":1736595328000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10,11]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1002\/net.20144"],"URL":"https:\/\/doi.org\/10.1002\/net.20144","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[2006,10,11]]}}}