{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T23:52:57Z","timestamp":1770508377315,"version":"3.49.0"},"reference-count":54,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":10541,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1977,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>When solving multicommodity network flow problems with either a primal or a dual partitioning technique one must carry and update a working basis inverse whose size need never exceed the number of saturated arcs (i.e. arcs for which there is no excess capacity). Efficient procedures have appeared in the literature for updating this inverse if it is carried in explicit form. However, for real world multicommodity network flow problems, this inverse may become quite large. In addition, this matrix may be quite dense even though the working basis may be sparse. In an attempt to obtain a sparse representation of this inverse matrix and simplify the computational burden, we present a new data structure along with the updating formulae for storing and updating this matrix. This data structure is a generalization of the well\u2010known product form procedure frequently used in mathematical programming codes.<\/jats:p>","DOI":"10.1002\/net.3230070403","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T06:18:18Z","timestamp":1178864298000},"page":"297-322","source":"Crossref","is-referenced-by-count":6,"title":["A product form representation of the inverse of a multicommodity cycle matrix"],"prefix":"10.1002","volume":"7","author":[{"given":"R. V.","family":"Helgason","sequence":"first","affiliation":[]},{"given":"J. L.","family":"Kennington","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Presented at Joint National Meeting of ORSA\/TIMS","author":"Barr R. S.","year":"1975"},{"key":"e_1_2_1_3_2","volume-title":"Linear Programming and Network Flows","author":"Bazaraa M. S.","year":"1977"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.5.1.36"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.636"},{"key":"e_1_2_1_6_2","unstructured":"Bradley G. H.andG. G.Brown \u201cA Comparison of Storage Structures for Primal Network Codes \u201dPresented at Joint National Meeting of ORSA\/TIMS Chicago April1975."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1080\/05695557508975006"},{"key":"e_1_2_1_8_2","volume-title":"ORC 65\u201335","author":"Bradley S. P.","year":"1965"},{"key":"e_1_2_1_9_2","first-page":"85","volume-title":"Theory of Traffic Flow","author":"Charnes A.","year":"1961"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(74)90062-8"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0038-0121(68)90014-1"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800170303"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.1.97"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.822"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.5.783"},{"key":"e_1_2_1_16_2","first-page":"3","article-title":"Augmented Threaded Index Method for Network Optimization","volume":"12","author":"Glover F.","year":"1974","journal-title":"INFOR"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040302"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/355626.355634"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580655"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584987"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800170402"},{"key":"e_1_2_1_22_2","first-page":"4","article-title":"A Generalized Upper Bounding Algorithm for Multicommodity Network Flow Problems","volume":"1","author":"Hartman J. K.","year":"1972","journal-title":"Networks"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580223"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1080\/05695557708975122"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584086"},{"key":"e_1_2_1_26_2","volume-title":"ORC 66\u201324","author":"Jewell W. S.","year":"1966"},{"key":"e_1_2_1_27_2","volume-title":"ORC 65\u20131","author":"Johnson E.","year":"1965"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.619"},{"key":"e_1_2_1_29_2","unstructured":"Jorgensen N. O. \u201cSome Aspects of the Urban Traffic Assignment Problem \u201d Graduate Report Institute of Transportation and Traffic Engineering University of California Berkeley 1963."},{"key":"e_1_2_1_30_2","doi-asserted-by":"crossref","unstructured":"Kalan J. E. \u201cAspects of Large\u2010Scale In\u2010Core Linear Programming \u201d Proc. of 1971 Annual Conference of the ACM Chicago Illinois pp.304\u2013313.","DOI":"10.1145\/800184.810500"},{"key":"e_1_2_1_31_2","unstructured":"Karney D.andD.Klingman \u201cImplementation and Computational Study of an In\u2010Core Out\u2010of\u2010Core Primal Network Code \u201dResearch Report 158 Center for Cybernetic Studies The University of Texas at Austin October1973."},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","unstructured":"Kaul R. N. \u201cAn Extension of Generalized Upper Bounded Techniques for Linear Programming \u201dORC 65\u201327 University of California Berkeley 1965.","DOI":"10.21236\/AD0623465"},{"key":"e_1_2_1_33_2","unstructured":"Kennington J. \u201cSolving Multicommodity Transportation Problems Using a Primal Partitioning Simplex Technique \u201d to appear inNaval Research Logistics Quarterly."},{"key":"e_1_2_1_34_2","article-title":"A State\u2010of\u2010the\u2010Art Survey of Multicommodity Network Flows","author":"Kennington J.","journal-title":"Operations Research."},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.9.994"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.1.91"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800210407"},{"key":"e_1_2_1_38_2","volume-title":"Optimization Theory for Large Systems","author":"Lasdon L. S.","year":"1970"},{"key":"e_1_2_1_39_2","first-page":"34","article-title":"Multicommodity Flows in a Communication Network","volume":"52","author":"Naniwada M.","year":"1969","journal-title":"Electronics and Communications in Japan"},{"key":"e_1_2_1_40_2","volume-title":"Advanced Linear\u2010Programming Computing Techniques","author":"Orchard\u2010Hays W.","year":"1968"},{"key":"e_1_2_1_41_2","volume-title":"Flows in Transportation Networks","author":"Potts R. B.","year":"1972"},{"key":"e_1_2_1_42_2","volume-title":"Presented at 8th International Symposium on Mathematical Programming","author":"Powell S.","year":"1973"},{"key":"e_1_2_1_43_2","volume-title":"ORC Report 66\u201324","author":"Saigal R.","year":"1966"},{"key":"e_1_2_1_44_2","volume-title":"ORC Report 66\u201325","author":"Sakarovitch M.","year":"1966"},{"key":"e_1_2_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/321752.321754"},{"key":"e_1_2_1_46_2","volume-title":"Working Paper No. 184","author":"Swoveland C.","year":"1971"},{"key":"e_1_2_1_47_2","first-page":"3","article-title":"A Two\u2010Stage Decomposition Algorithm for a Generalized Multi\u2010Commodity Flow Problem","volume":"11","author":"Swoveland C.","year":"1973","journal-title":"INFOR"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.1.45"},{"key":"e_1_2_1_49_2","first-page":"263","article-title":"A Linear Programming Model for the Assignment of Traffic","volume":"3","author":"Tomlin J. A.","year":"1966","journal-title":"Proc. of Third Conference of the Australian Road Research Board"},{"key":"e_1_2_1_50_2","unstructured":"Tomlin J. A. \u201cMathematical Programming Models for Traffic Network Problems \u201d unpublished dissertation Department of Mathematics University of Adelaide Australia 1967."},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800190106"},{"key":"e_1_2_1_52_2","unstructured":"White W. W.andE.Wrathall \u201cA System for Railroad Traffic Scheduling \u201dTech. Report No. 320\u20132993 IBM\u2010Philadelphia Scientific Center 1970."},{"key":"e_1_2_1_53_2","unstructured":"White W. W. \u201cMathematical Programming Multicommodity Flows and Communication Nets \u201dProc. of Symposium on Computer\u2010Communications Networks and Teletraffic Polytechnic Institute of Brooklyn 1972 pp.325\u2013334."},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010304"},{"key":"e_1_2_1_55_2","first-page":"511","volume-title":"Integer and Nonlinear Programming","author":"Zoutendijk G.","year":"1970"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230070403","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230070403","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T09:51:27Z","timestamp":1699782687000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230070403"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1977,12]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1977,12]]}},"alternative-id":["10.1002\/net.3230070403"],"URL":"https:\/\/doi.org\/10.1002\/net.3230070403","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1977,12]]}}}