{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T11:03:48Z","timestamp":1776942228915,"version":"3.51.4"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T00:00:00Z","timestamp":1640649600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T00:00:00Z","timestamp":1640649600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001663","name":"Volkswagen Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The robust minimum cost flow problem under consistent flow constraints (RobMCF<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\equiv $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2261<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) is a new extension of the minimum cost flow (MCF) problem. In the RobMCF<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\equiv $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2261<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problem, we consider demand and supply that are subject to uncertainty. For all demand realizations, however, we require that the flow value on an arc needs to be equal if it is included in the predetermined arc set given. The objective is to find feasible flows that satisfy the equal flow requirements while minimizing the maximum occurring cost among all demand realizations. In the case of a finite discrete set of scenarios, we derive structural results which point out the differences with the polynomial time solvable MCF problem in networks with integral demands, supplies, and capacities. In particular, the Integral Flow Theorem of Dantzig and Fulkerson does not hold. For this reason, we require integral flows in the entire paper. We show that the RobMCF<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\equiv $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2261<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problem is strongly <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard on acyclic digraphs by a reduction from the (3,\u00a0<jats:italic>B<\/jats:italic>2)-<jats:sc>Sat<\/jats:sc> problem. Further, we demonstrate that the RobMCF<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\equiv $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2261<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problem is weakly <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard on series-parallel digraphs by providing a reduction from <jats:sc>Partition<\/jats:sc>. If in addition the number of scenarios is constant, we propose a pseudo-polynomial algorithm based on dynamic programming. Finally, we present a special case on series-parallel digraphs for which we can solve the RobMCF<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\equiv $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2261<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problem in polynomial time.<\/jats:p>","DOI":"10.1007\/s10479-021-04426-0","type":"journal-article","created":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T03:02:22Z","timestamp":1640660542000},"page":"691-722","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Robust minimum cost flow problem under consistent flow constraints"],"prefix":"10.1007","volume":"312","author":[{"given":"Christina","family":"B\u00fcsing","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arie M. C. A.","family":"Koster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4969-4552","authenticated-orcid":false,"given":"Sabrina","family":"Schmitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,12,28]]},"reference":[{"key":"4426_CR1","doi-asserted-by":"crossref","unstructured":"Ahuja, R.K., Magnanti,T.L., & Orlin,J.B. (1988). Network flows.","DOI":"10.21236\/ADA594171"},{"issue":"10","key":"4426_CR2","doi-asserted-by":"publisher","first-page":"1440","DOI":"10.1287\/mnsc.45.10.1440","volume":"45","author":"RK Ahuja","year":"1999","unstructured":"Ahuja, R. K., Orlin, J. B., Sechi, G. M., & Zuddas, P. (1999). Algorithms for the simple equal flow problem. Management Science, 45(10), 1440\u20131455.","journal-title":"Management Science"},{"issue":"1","key":"4426_CR3","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0377-2217(88)90012-4","volume":"36","author":"AI Ali","year":"1988","unstructured":"Ali, A. I., Kennington, J., & Shetty, B. (1988). The equal flow problem. European Journal of Operational Research, 36(1), 107\u2013115.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"4426_CR4","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1002\/net.20145","volume":"49","author":"A Altin","year":"2007","unstructured":"Altin, A., Amaldi, E., Belotti, P., & Pinar, M. \u00c7. (2007). Provisioning virtual private networks under traffic uncertainty. Networks, 49(1), 100\u2013155.","journal-title":"Networks"},{"issue":"1","key":"4426_CR5","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1287\/ijoc.1100.0380","volume":"23","author":"A Altin","year":"2011","unstructured":"Altin, A., Yaman, H., & Pinar, M. (2011). The robust network loading problem under hose demand uncertainty: formulation, polyhedral analysis, and computations. INFORMS Journal on Computing, 23(1), 75\u201389.","journal-title":"INFORMS Journal on Computing"},{"key":"4426_CR6","doi-asserted-by":"crossref","unstructured":"\u00c1lvarez-Miranda, E., Cacchiani, V., Dorneth, T., J\u00fcnger, M., Liers, F., Lodi, A., Parriani, T., & Schmidt, D.R. (2012). Models and algorithms for robust network design with several traffic scenarios. In A. Ridha Mahjoub, V. Markakis, I. Milis, V.T. Paschos (Eds), ISCO 2012, revised selected papers (vol 7422, pp. 261\u2013272),","DOI":"10.1007\/978-3-642-32147-4_24"},{"issue":"4","key":"4426_CR7","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1287\/opre.1070.0428","volume":"55","author":"A Atamt\u00fcrk","year":"2007","unstructured":"Atamt\u00fcrk, A., & Zhang, M. (2007). Two-stage robust network flow and design under demand uncertainty. Operations Research, 55(4), 662\u2013673.","journal-title":"Operations Research"},{"issue":"2","key":"4426_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0166-218X(85)90006-X","volume":"10","author":"WW Bein","year":"1985","unstructured":"Bein, W. W., Brucker, P., & Tamir, A. (1985). Minimum cost flow algorithms for series-parallel networks. Discrete Applied Mathematics, 10(2), 117\u2013124.","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"4426_CR9","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1016\/j.comnet.2008.01.005","volume":"52","author":"P Belotti","year":"2008","unstructured":"Belotti, P., Capone, A., Carello, G., & Malucelli, F. (2008). Multi-layer mpls network design: the impact of statistical multiplexing. Computer Networks, 52(6), 1291\u20131307.","journal-title":"Computer Networks"},{"key":"4426_CR10","unstructured":"Berman, P., Karpinski, M., & Scott, A. (2004). Approximation hardness of short symmetric instances of max-3sat. Technical report"},{"issue":"1","key":"4426_CR11","first-page":"49","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas, D., & Sim, M. (2003). Robust Discrete Optimization and Network Flows, 98(1), 49\u201371.","journal-title":"Robust Discrete Optimization and Network Flows"},{"issue":"1","key":"4426_CR12","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35\u201353.","journal-title":"Operations Research"},{"issue":"1","key":"4426_CR13","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s10107-016-0991-9","volume":"157","author":"V Cacchiani","year":"2016","unstructured":"Cacchiani, V., J\u00fcnger, M., Liers, F., Lodi, A., & Schmidt, D. R. (2016). Single-commodity robust network design with finite and hose demand sets. Mathematical Programming, 157(1), 297\u2013342.","journal-title":"Mathematical Programming"},{"issue":"3","key":"4426_CR14","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1016\/S0377-2217(02)00505-2","volume":"150","author":"HI Calvete","year":"2003","unstructured":"Calvete, H. I. (2003). Network simplex algorithm for the general equal flow problem. European Journal of Operational Research, 150(3), 585\u2013600.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"4426_CR15","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0377-2217(84)90068-7","volume":"16","author":"P Carraresi","year":"1984","unstructured":"Carraresi, P., & Gallo, G. (1984). Network models for vehicle and crew scheduling. European Journal of Operational Research, 16(2), 139\u2013151.","journal-title":"European Journal of Operational Research"},{"key":"4426_CR16","doi-asserted-by":"crossref","unstructured":"Even, S., Itai, A., Shamir, A. (1975). On the complexity of time table and multi-commodity flow problems. In 16th annual symposium on foundations of computer science (sfcs 1975) (pp. 184\u2013193). IEEE.","DOI":"10.1109\/SFCS.1975.21"},{"key":"4426_CR17","unstructured":"Johnson, D.S., & Garey, M.R. (1979) Computers and intractability: A guide to the theory of NP-completeness. WH Freeman."},{"key":"4426_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial optimization","author":"B Korte","year":"2012","unstructured":"Korte, B., Vygen, J., Korte, B., & Vygen, J. (2012). Combinatorial optimization (Vol. 2). Berlin: Springer."},{"issue":"2","key":"4426_CR19","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1002\/net.21497","volume":"61","author":"AMCA Koster","year":"2013","unstructured":"Koster, A. M. C. A., Kutschka, M., & Raack, C. (2013). Robust network design: formulations, valid inequalities, and computations. Networks, 61(2), 128\u2013149. https:\/\/doi.org\/10.1002\/net.21497.","journal-title":"Networks"},{"issue":"11","key":"4426_CR20","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/j.ipl.2011.03.007","volume":"111","author":"SO Krumke","year":"2011","unstructured":"Krumke, S. O., & Thielen, C. (2011). Minimum cost flows with minimum quantities. Information Processing Letters, 111(11), 533\u2013537.","journal-title":"Information Processing Letters"},{"issue":"4","key":"4426_CR21","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW LenstraJr","year":"1983","unstructured":"LenstraJr, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538\u2013548.","journal-title":"Mathematics of Operations Research"},{"issue":"13","key":"4426_CR22","doi-asserted-by":"publisher","first-page":"3665","DOI":"10.1007\/s11269-010-9625-9","volume":"24","author":"A Manca","year":"2010","unstructured":"Manca, A., Sechi, G. M., & Zuddas, P. (2010). Water supply network optimisation using equal flow algorithms. Water Resources Management, 24(13), 3665\u20133678.","journal-title":"Water Resources Management"},{"key":"4426_CR23","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s10589-012-9500-0","volume":"54","author":"S Mattia","year":"2013","unstructured":"Mattia, S. (2013). The robust network loading problem with dynamic routing. Computational Optimization and Applications, 54, 619\u2013643.","journal-title":"Computational Optimization and Applications"},{"issue":"4","key":"4426_CR24","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.orl.2009.03.006","volume":"37","author":"CA Meyers","year":"2009","unstructured":"Meyers, C. A., & Schulz, A. S. (2009). Integer equal flows. Operations Research Letters, 37(4), 245\u2013249.","journal-title":"Operations Research Letters"},{"issue":"3","key":"4426_CR25","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/net.3230190305","volume":"19","author":"M Minoux","year":"1989","unstructured":"Minoux, M. (1989). Networks synthesis and optimum network design problems: models, solution methods and applications. Networks, 19(3), 313\u2013360.","journal-title":"Networks"},{"issue":"1","key":"4426_CR26","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1287\/ijoc.1110.0485","volume":"25","author":"DR Morrison","year":"2013","unstructured":"Morrison, D. R., Sauppe, J. J., & Jacobson, S. H. (2013). A network simplex algorithm for the equal flow problem on a generalized network. INFORMS Journal on Computing, 25(1), 2\u201312.","journal-title":"INFORMS Journal on Computing"},{"key":"4426_CR27","unstructured":"Ohst, J.P. (2016). On the construction of optimal paths from flows and the analysis of evacuation scenarios."},{"issue":"1","key":"4426_CR28","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10878-011-9438-7","volume":"26","author":"U Pferschy","year":"2013","unstructured":"Pferschy, U., & Schauer, J. (2013). The maximum flow problem with disjunctive constraints. Journal of Combinatorial Optimization, 26(1), 109\u2013119.","journal-title":"Journal of Combinatorial Optimization"},{"key":"4426_CR29","doi-asserted-by":"crossref","unstructured":"Poss, M., & Raack, C. (2013). Affine recourse for the robust network design problem: between static and dynamic routing. Networks, 61(2)","DOI":"10.1002\/net.21482"},{"issue":"4","key":"4426_CR30","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S Sahni","year":"1974","unstructured":"Sahni, S. (1974). Computationally related problems. SIAM Journal on Computing, 3(4), 262\u2013279.","journal-title":"SIAM Journal on Computing"},{"key":"4426_CR31","unstructured":"Sanit\u00e0, L. (2009). Robust Network Design. PhD thesis, Universit\u00e0 La Sapienza, Roma."},{"key":"4426_CR32","doi-asserted-by":"crossref","unstructured":"Seedig, H.G. (2009). Network flow optimization with minimum quantities. In Operations research proceedings 2010 pp. 295\u2013300. Springer.","DOI":"10.1007\/978-3-642-20009-0_47"},{"key":"4426_CR33","doi-asserted-by":"crossref","unstructured":"Srinathan, K., Goundan, P.R., Kumar, M.V., Nandakumar, R., & Rangan, C.P. (2002). Theory of equal-flows in networks. In O.H. Ibarra, L. Zhang, (Eds), Computing and combinatorics (pp. 514\u2013524), Berlin, Heidelberg, Springer Berlin Heidelberg. ISBN 978-3-540-45655-1.","DOI":"10.1007\/3-540-45655-4_55"},{"key":"4426_CR34","doi-asserted-by":"publisher","unstructured":"Valdes,J., Tarjan,R.E., & Lawler, E.L. (1979). The recognition of series parallel digraphs. In Proceedings of the eleventh annual ACM symposium on theory of computing, STOC \u201979 (pp. 1\u201312) New York, NY, USA, ACM. https:\/\/doi.org\/10.1145\/800135.804393.","DOI":"10.1145\/800135.804393."},{"issue":"2","key":"4426_CR35","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R. E., & Lawler, E. L. (1982). The recognition of series parallel digraphs. SIAM Journal on Computing, 11(2), 298\u2013313.","journal-title":"SIAM Journal on Computing"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04426-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-021-04426-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-021-04426-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T01:15:47Z","timestamp":1654823747000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-021-04426-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,28]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["4426"],"URL":"https:\/\/doi.org\/10.1007\/s10479-021-04426-0","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,28]]},"assertion":[{"value":"10 November 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}