{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:09:59Z","timestamp":1787389799166,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1333260"],"award-info":[{"award-number":["CMMI-1333260"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"We provide a simplex algorithm for a structured class of uncapacitated countably infinite network flow problems. Previous efforts required explicit capacities on arcs with uniformity properties that facilitate duality arguments. By contrast, this paper takes a \u201cprimal\u201d approach by devising a simplex method that provably converges to the optimal value using arguments based on convergence of spanning trees and nonnegativity of reduced costs. This allows for removal of explicit capacity bounds. The method also converges, on a subsequence, to an extremal optimal solution. Our method is tailored to our problem setting---acyclic networks with nodes of only nonnegative supplies (or, alternatively, only demands). The necessary structure can be found in a variety of applied settings not amenable to existing methods, including nonstationary infinite-horizon dynamic programming. A finite implementation of our simplex algorithm is provided for the infinite horizon dynamic lot-sizing problem under linear costs.<\/jats:p>","DOI":"10.1137\/17m1137553","type":"journal-article","created":{"date-parts":[[2018,7,17]],"date-time":"2018-07-17T11:37:08Z","timestamp":1531827428000},"page":"2022-2048","source":"Crossref","is-referenced-by-count":8,"title":["A Simplex Method for Uncapacitated Pure-supply Infinite Network Flow Problems"],"prefix":"10.1137","volume":"28","author":[{"given":"Christopher Thomas","family":"Ryan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert L.","family":"Smith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marina A.","family":"Epelman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2010.08.002"},{"key":"atypb2","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin,\n Network Flows: Theory, Algorithms, and Applications\n , Prentice-Hall, Upper Saddle River, NJ, 1993."},{"key":"atypb3","unstructured":"C. Aliprantis and K. Border,\n Infinite Dimensional Analysis: A Hitchhiker's Guide\n , 3rd ed., Springer-Verlag, Berlin, 2006."},{"key":"atypb4","unstructured":"E. J. Anderson and P. Nash,\n Linear Programming in Infinite-Dimensional Spaces: Theory and Applications\n , Wiley, New York, 1987."},{"key":"atypb5","unstructured":"D. Bertsimas and J. Tsitsiklis,\n Introduction to Linear Optimization\n , Athena Scientific, Nashua, NH, 1997."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580379"},{"key":"atypb7","unstructured":"E. Denardo,\n Dynamic Programming: Models and Applications\n , Dover, New York, 2003."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n Graph Theory\n , 4th ed., Springer-Verlag, Berlin, 2010.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.04.026"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/16M1084328"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0755"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2008.09.002"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1121"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2017.1598"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/net.21754"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00935175"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012993257507"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2016.01.005"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/net.20134"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1287\/moor.23.1.239"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585695"},{"key":"atypb22","unstructured":"W. Rudin,\n Principles of Mathematical Analysis\n , 3rd ed., McGraw-Hill, New York, 1976."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586057"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1002\/net.20221"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.1.89"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1137553","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:18:44Z","timestamp":1787339924000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1137553"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1137553"],"URL":"https:\/\/doi.org\/10.1137\/17m1137553","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}