Solving Robust Variants of Integer Flow Problems with Uncertain Arc Capacities
Abstract
This paper deals with robust optimization and network flows. Several robust variants of integer flow problems are considered. They assume uncertainty of network arc capacities as well as of arc unit costs (where applicable). Uncertainty is expressed by discrete scenarios. Since the considered variants of the maximum flow problem are easy to solve, the paper is mostly concerned with NP-hard variants of the minimum-cost flow problem, thus proposing an approximate algorithm for their solution. The accuracy of the proposed algorithm is verified by experiments.
References
Bazaraa MS, Jarvis JJ, Sherali HD. Linear Programming and Network Flows. Fourth Edition. Hoboken NJ: Wiley; 2010.
Jungnickel D. Graphs, Networks and Algorithms. Fourth Edition. Springer, Berlin; 2013.
Papadimitriou CH, Steiglitz K. Combinatorial Optimization – Algorithms and Complexity. Mineola NY: Dover Publications; 1998.
Ben-Tal A, El Ghaoui L, Nemirovski A. Robust Optimization. Princeton NJ: Princeton University Press; 2009.
Bertsimas D, Sim M. Robust discrete optimization and network flows. Mathematical Programming. 2003;98: 49-71.
Bertsimas D, Sim M. The price of robustness. Operations Research. 2004;52: 35-53.
Kouvelis P, Yu G. Robust Discrete Optimization and Its Applications. Berlin: Springer; 1997.
Aissi H, Bazgan C, Vanderpooten D. Min-max and min-max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research. 2009;197: 427-438.
Aissi H, Bazgan C, Vanderpooten D. General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems. Discrete Optimizaton. 2010;7: 136-148.
Bertsimas D, Brown DB, Caramanis C. Theory and applications of robust optimization. SIAM Review. 2011;53: 464-501.
Kasperski A, Zielinski P. Robust discrete optimization under discrete and interval uncertainty: A survey. In: Doumpos M, Zopounidis C, Grigoroudis E. (eds.) Robustness Analysis in Decision Aiding, Optimization, and Analytics. Cham CH: Springer; 2016. p. 113-143.
Aissi H, Vanderpooten D. Robust capacity expansion of a network under demand uncertainty: A bi-objective approach. Networks. 2016;68: 185-199.
Atamtürk A, Zhang M. Two-stage robust network flow and design under demand uncertainty. Operations Research. 2007;55: 662-673.
Bertsimas D, Nasrabadi E, Stiller S. Robust and adaptive network flows. Operations Research. 2013;61: 1218-1242.
Boginski VL, Commander CW, Turko T. Polynomial-time identification of robust network flows under uncertain arc failures. Optimization Letters. 2009;3: 461-473.
Minoux M. On robust maximum flow with polyhedral uncertainty sets. Optimization Letters. 2009;3: 367-376.
Minoux M. Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Applied Mathematics. 2010;158: 597-603.
Ordoñez F, Zhao J. Robust capacity expansion of network flows. Networks. 2007;50: 136-145.
Poss M. A comparison of routing sets for robust network design. Optimization Letters. 2014;8: 1619-1635.
Righetto GM, Morabito R, Alem D. A robust optimization approach for cash flow management in stationery companies. Computers and Industrial Engineering. 2016;99: 137-152.
Rui M, Jinfu Z. Robust discrete optimization for the minimum cost flow problem. In: Wang C, Ye Z. (eds.) Proceedings of the International Workshop on Intelligent Systems and Applications – ISA 2009. Wuhan, China, 23-24 May 2009. Piscataway NJ: IEEE; 2009. p. 1-4.
Špoljarec M, Manger R. Heuristic solutions to robust variants of the minimum-cost integer flow problem. Journal of Heuristics. 2020;26: 531-559.
Eiben AE, Smith JE. Introduction to Evolutionary Computing. Second edition. Berlin: Springer; 2015.
Talbi EG. Metaheuristics – From Design to Implementation. Hoboken NJ: Wiley; 2009.
Korte B, Vygen J. Combinatorial Optimization – Theory and Algorithms. Fifth Edition. Berlin: Springer; 2012.
Carre B. Graphs and Networks. Oxford UK: Oxford University Press; 1979.
IBM Corporation. IBM ILOG CPLEX Optimization Studio, CPLEX User's Manual, Version 12, Release 8. IBM Knowledge Center; 2017. Available from: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0 [Accessed 17 Dec 2018].
Troelsen A, Japikse P. C# 6.0 and the .NET 4.6 Framework. 7th Edition. New York NY: Apress; 2016.
Beasley JE. OR-Library. Brunel University London; 2018. Available from: http://people.brunel.ac.uk/~mastjjb/jeb/info.html [Accessed 17 Dec 2018].
DIMACS – Center for Discrete Mathematics and Theoretical Computer Science. DIMACS Implementation Challenges. Piscataway NJ: Rutgers University; 2017. Available from: http://archive.dimacs.rutgers.edu/Challenges [Accessed 17 Dec 2018].
Copyright (c) 2021 Marko Špoljarec, Robert Manger
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
