×

Rapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problems. (English) Zbl 1214.90099

Summary: The Minimum Capacity \(s\)-\(t\) Cut Problem (MinCut) is an intensively studied problem in combinatorial optimization. A natural extension is the problem of choosing a minimum capacity \(s\)-\(t\) cut when arc capacities are unknown but confined to known intervals. This motivates the Robust Minimum Capacity \(s\)-\(t\) Cut Problem (RobuCut), which has applications such as open-pit mining and project scheduling. In this paper, we show how RobuCut can be reduced to solving a sequence of maximum flow problems and provide an efficient algorithm for rapidly solving this sequence of problems. We demonstrate that our algorithm solves instances of RobuCut in seconds that would require hours if a standard maximum flow solver is iteratively used as a black-box subroutine.

MSC:

90C27 Combinatorial optimization

Software:

Netsoft
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: theory, algorithms and applications. New York: Prentice Hall. · Zbl 1201.90001
[2] Altner, D. S. (2008). Advancements on problems involving maximum flows. Ph.D. Thesis, Georgia Institute of Technology, Atlanta, Georgia. · Zbl 1142.90493
[3] Altner, D. S., & Ergun, Ö. (2008). Rapidly solving an online sequence of maximum flow problems with applications to computing robust minimum cuts. In L. Perron & M. A. Trick (Eds.), Lecture Notes in Computer Science: Vol. 5015. Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. Berlin: Springer. · Zbl 1142.90493
[4] Atamtürk, A., & Zhang, M. (2007). Two-stage robust network flow and design under demand uncertainty. Operations Research, 55, 662–673. · Zbl 1167.90409 · doi:10.1287/opre.1070.0428
[5] Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23, 769–805. · Zbl 0977.90052 · doi:10.1287/moor.23.4.769
[6] Bertsimas, D., & Sim, M. (2003). Robust discrete optimization and network flows. Mathematical Programming, 98, 49–71. · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4
[7] Chaerani, D., & Roos, C. (2006). Modelling some robust design problems via conic optimization. Operations Research Proceedings, 209–214. · Zbl 1209.90288
[8] Cheriyan, J., & Melhorn, K. (1999). An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters, 69, 239–242. · Zbl 1338.68097 · doi:10.1016/S0020-0190(99)00019-8
[9] Cherkassky, B. V., & Goldberg, A. V. (1994). On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19, 390–410. · Zbl 0898.68029 · doi:10.1007/PL00009180
[10] Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399–404. · Zbl 0073.40203 · doi:10.4153/CJM-1956-045-5
[11] Goldberg, A. V. (2010). Andrew V. Goldberg’s network optimization library. http://avglab.com/andrew/soft.html .
[12] Goldberg, A. V., & Rao, S. (1998). Beyond the flow decomposition barrier. Journal of Associated Computing Machinery, 45, 783–797. · Zbl 1064.90567 · doi:10.1145/290179.290181
[13] Goldberg, A. V., & Tarjan, R. E. (1988). A new approach to the maximum flow problem. Journal of Associated Computing Machinery, 35, 921–940. · Zbl 0661.90031 · doi:10.1145/48014.61051
[14] Govindaraju, V. (2008). Professor of computer science and engineering, University of Buffalo, personal communication.
[15] Harris, T. E., & Ross, F. S. (1955). Fundamentals of a method for evaluating rail network capacities. Research Memorandum RM-1573, The RAND Corporation, Santa Monica, CA.
[16] Hochbaum, D. S., & Chen, A. (2000). Improved planning for the open-pit mining problem. Operations Research, 48, 894–914. · doi:10.1287/opre.48.6.894.12392
[17] Matsuoka, Y., & Fujishige, S. (2004). Practical efficiency of maximum flow algorithms using maximum adjacency (MA) orderings. Technical Report METR 2004-27, University of Tokyo. · Zbl 1122.90087
[18] Möhring, R. H., Schulz, A. S., Stork, F., & Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49, 330–350. · Zbl 1232.90213 · doi:10.1287/mnsc.49.3.330.12737
[19] Monkhouse, P. H. L., & Yeates, G. (2005). Beyond naive optimization. AUSIMM Spectrum Series, 14, 3–8.
[20] Ordóñez, F., & Zhao, J. (2007). Robust capacity expansion of network flows. Networks, 50, 136–145. · Zbl 1144.90325 · doi:10.1002/net.20183
[21] Régin, J. C. (1994). A filtering algorithm for constraints of difference in constraint satisfaction problems. In Proceedings of the twelfth national conference on artificial intelligence, vol. 1, pp. 362–367.
[22] Royset, J. O., & Wood, R. K. (2007). Solving the bi-objective maximum flow network interdiction problem. INFORMS Journal on Computing, 19, 175–184. · Zbl 1241.90139 · doi:10.1287/ijoc.1060.0191
[23] Stone, H. S. (1977). Multiprocessor scheduling with the aid of network flow algorithms. IEEE Transactions on Software Engineering, 3, 85–93. · Zbl 0355.68042 · doi:10.1109/TSE.1977.233840
[24] Strickland, D. M., Barnes, E., & Sokol, J. S. (2005). Optimal protein structure alignment using maximum cliques. Operations Research, 53, 389–402. · Zbl 1165.90664 · doi:10.1287/opre.1040.0189
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.