×

Minimum-cost flow algorithms: an experimental evaluation. (English) Zbl 1320.90095

Summary: An extensive computational analysis of several algorithms for solving the minimum-cost network flow problem is conducted. Some of the considered implementations were developed by the author and are available as part of an open-source C++ optimization library called LEMON (http://lemon.cs.elte.hu/). These codes are compared to other publicly available solvers: CS2, MCF, RelaxIV, PDNET, MCFSimplex, as well as the corresponding components of the IBM ILOG CPLEX Optimization Studio and the LEDA C++ library. This evaluation, to the author’s knowledge, is more comprehensive than earlier studies in terms of the range of considered implementations as well as the diversity and size of problem instances. The presented results demonstrate that the primal network simplex and cost-scaling algorithms are the most efficient and robust in general. Other methods, however, can outperform them in particular cases. The network simplex code of the author turned out to be far superior to the other implementations of this method, and it is the most efficient solver on the majority of the considered problem instances. In contrast, the cost-scaling algorithms tend to show better asymptotic behaviour, especially on sparse graphs, and hence they are typically faster than simplex-based methods on huge networks.

MSC:

90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja R., Tech. Rep. Sloan W.P. No. 2047-88 (1988)
[2] DOI: 10.1007/BF01585705 · Zbl 0761.90036 · doi:10.1007/BF01585705
[3] Ahuja R., Network Flows: Theory, Algorithms, and Applications (1993) · Zbl 1201.90001
[4] Armstrong R., Math. Program 78 pp 131– (1997)
[5] DOI: 10.1016/0377-2217(80)90193-9 · Zbl 0442.90100 · doi:10.1016/0377-2217(80)90193-9
[6] DOI: 10.1137/0218039 · Zbl 0674.90025 · doi:10.1137/0218039
[7] DOI: 10.1007/BF01584319 · Zbl 0378.90097 · doi:10.1007/BF01584319
[8] Barr R., INFOR 17 pp 16– (1979)
[9] DOI: 10.1007/BF01589405 · Zbl 0664.90031 · doi:10.1007/BF01589405
[10] DOI: 10.1007/BF02288322 · doi:10.1007/BF02288322
[11] DOI: 10.1287/opre.36.1.93 · Zbl 0662.90027 · doi:10.1287/opre.36.1.93
[12] Bertsekas D., Tech. Rep. LIDS-P-2276 (1994)
[13] Bland R., Tech. Rep. 661 (1985)
[14] DOI: 10.1007/BF01586039 · Zbl 0767.90013 · doi:10.1007/BF01586039
[15] Bland R., Network Flows and Matching: First DIMACS Implementation Challenge 12 pp 119– (1993)
[16] DOI: 10.1287/mnsc.24.1.1 · Zbl 0373.90079 · doi:10.1287/mnsc.24.1.1
[17] DOI: 10.1137/1.9781611973105.85 · doi:10.1137/1.9781611973105.85
[18] DOI: 10.1080/10556789808805709 · Zbl 0949.90008 · doi:10.1080/10556789808805709
[19] Busacker R., Tech. Rep. ORO-TP-15 (1960)
[20] DOI: 10.1007/PL00009180 · Zbl 0898.68029 · doi:10.1007/PL00009180
[21] DOI: 10.1007/BF01580379 · Zbl 0352.90039 · doi:10.1007/BF01580379
[22] Dantzig G., Activity Analysis of Production and Allocation pp 359– (1951)
[23] Dantzig G., Linear Programming and Extensions (1963) · Zbl 0108.33103 · doi:10.1515/9781400884179
[24] DOI: 10.1145/1027084.1027085 · Zbl 05456765 · doi:10.1145/1027084.1027085
[25] DOI: 10.1109/43.728912 · Zbl 05447838 · doi:10.1109/43.728912
[26] DOI: 10.1016/j.entcs.2011.06.003 · doi:10.1016/j.entcs.2011.06.003
[27] Edmonds J., Combinatorial Structures and Their Applications pp 93– (1970)
[28] DOI: 10.1145/321694.321699 · Zbl 0318.90024 · doi:10.1145/321694.321699
[29] DOI: 10.1287/opre.6.3.419 · doi:10.1287/opre.6.3.419
[30] Ford L., Flows in Networks (1962) · Zbl 0106.34802
[31] DOI: 10.1287/ijoc.1040.0081 · Zbl 1241.90158 · doi:10.1287/ijoc.1040.0081
[32] Frank A., Connections in Combinatorial Optimization (2011) · Zbl 1228.90001
[33] DOI: 10.1145/28869.28874 · doi:10.1145/28869.28874
[34] DOI: 10.1007/BF01580882 · Zbl 0597.90029 · doi:10.1007/BF01580882
[35] DOI: 10.1137/0109002 · Zbl 0112.12401 · doi:10.1137/0109002
[36] DOI: 10.1137/0218069 · Zbl 0679.68079 · doi:10.1137/0218069
[37] Z. Galil and E. Tardos,An Min-Cost Flow Algorithm, Proceedings of the 27th Symposium on Foundations of Computer Science, FOCS’86, IEEE Computer Society Press, Washington, DC, 1986, pp. 1–9. · Zbl 0652.90039
[38] DOI: 10.1145/42282.214090 · Zbl 0652.90039 · doi:10.1145/42282.214090
[39] DOI: 10.1137/1.9781611972894.1 · doi:10.1137/1.9781611972894.1
[40] DOI: 10.1287/mnsc.20.5.783 · Zbl 0303.90039 · doi:10.1287/mnsc.20.5.783
[41] DOI: 10.1006/jagm.1995.0805 · Zbl 05473508 · doi:10.1006/jagm.1995.0805
[42] DOI: 10.1007/978-3-540-87744-8_39 · Zbl 1158.90413 · doi:10.1007/978-3-540-87744-8_39
[43] Goldberg A., Network Flows and Matching: First DIMACS Implementation Challenge 12 pp 157– (1993)
[44] DOI: 10.1145/28395.28397 · doi:10.1145/28395.28397
[45] DOI: 10.1145/62212.62250 · doi:10.1145/62212.62250
[46] DOI: 10.1145/48014.61051 · Zbl 0661.90031 · doi:10.1145/48014.61051
[47] DOI: 10.1145/76359.76368 · Zbl 0697.68063 · doi:10.1145/76359.76368
[48] DOI: 10.1287/moor.15.3.430 · Zbl 0727.90024 · doi:10.1287/moor.15.3.430
[49] Goldberg A., Paths, Flows and VLSI-Layout pp 101– (1990)
[50] DOI: 10.1007/BF01758840 · Zbl 0761.90037 · doi:10.1007/BF01758840
[51] DOI: 10.1007/BFb0121089 · Zbl 0594.90025 · doi:10.1007/BFb0121089
[52] DOI: 10.1002/net.3230230607 · Zbl 0786.90081 · doi:10.1002/net.3230230607
[53] DOI: 10.1080/05695557708975122 · doi:10.1080/05695557708975122
[54] Howard R., The MIT Press (1960)
[55] Iri M., J. Oper. Res. Soc. Japan 3 pp 27– (1960)
[56] Jewell W., Tech. Rep. No. 8 (1958)
[57] DOI: 10.1287/opre.14.4.619 · doi:10.1287/opre.14.4.619
[58] D. Kelly and G. O’Neill,The minimum cost flow problem and the network simplex solution method, Ph.D. diss. University College, Dublin, 1991.
[59] Kennington J., Algorithms for Network Programming (1980) · Zbl 0502.90056
[60] Király Z., Acta Universitatis Sapientiae, Informatica 4 pp 67– (2012)
[61] DOI: 10.1287/mnsc.14.3.205 · Zbl 0178.22902 · doi:10.1287/mnsc.14.3.205
[62] DOI: 10.1287/mnsc.20.5.814 · Zbl 0303.90042 · doi:10.1287/mnsc.20.5.814
[63] DOI: 10.1007/978-3-642-24488-9 · Zbl 1237.90001 · doi:10.1007/978-3-642-24488-9
[64] DOI: 10.1002/nav.3800020109 · doi:10.1002/nav.3800020109
[65] Y. Lee,Computational analysis of network optimization algorithms, Ph.D. diss. Department of Civil and Environmental Engineering, (Supervisor: J.B. Orlin) MIT, Cambridge, MA, 1993.
[66] Löbel A., Tech. Rep. SC 96-7 (1996)
[67] Löbel A., MCF Version 1.3–A Network Simplex Implementation (2004)
[68] Mehlhorn K., LEDA: A Platform for Combinatorial and Geometric Computing (1999)
[69] DOI: 10.1098/rspa.1960.0144 · Zbl 0093.42106 · doi:10.1098/rspa.1960.0144
[70] DOI: 10.1145/322063.322070 · Zbl 0379.90101 · doi:10.1145/322063.322070
[71] Orlin J., Tech. Rep. 1615-84 (1984)
[72] DOI: 10.1145/62212.62249 · doi:10.1145/62212.62249
[73] DOI: 10.1287/opre.41.2.338 · Zbl 0781.90036 · doi:10.1287/opre.41.2.338
[74] Orlin J., Math. Program 78 pp 109– (1997)
[75] DOI: 10.1007/BF01580615 · Zbl 0784.90097 · doi:10.1007/BF01580615
[76] Plotkin S., Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, SODA’90 pp 367– (1990)
[77] Portugal L., Tech. Rep. TD-5X2SLN (2004)
[78] DOI: 10.1590/S0101-74382008000200005 · Zbl 1257.90107 · doi:10.1590/S0101-74382008000200005
[79] Resende M., Advances in Linear and Integer Programming pp 147– (1996)
[80] Resende M., Network Flows and Matching: First DIMACS Implementation Challenge 12 pp 299– (1993)
[81] DOI: 10.1002/net.10087 · Zbl 1054.90090 · doi:10.1002/net.10087
[82] Röck H., Discrete Structures and Algorithms pp 181– (1980)
[83] Schrijver A., Combinatorial Optimization: Polyhedra and Efficiency (2003) · Zbl 1041.90001
[84] J. Siek, L.Q. Lee, and A. Lumsdaine,The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley, Reading, PA, 2002.
[85] DOI: 10.2298/YJOR121120001S · Zbl 1299.90003 · doi:10.2298/YJOR121120001S
[86] DOI: 10.1016/0022-0000(83)90006-5 · Zbl 0509.68058 · doi:10.1016/0022-0000(83)90006-5
[87] DOI: 10.1002/1097-0037(200008)36:1<53::AID-NET6>3.0.CO;2-Y · Zbl 0969.90021 · doi:10.1002/1097-0037(200008)36:1<53::AID-NET6>3.0.CO;2-Y
[88] DOI: 10.1145/321752.321754 · Zbl 0257.68034 · doi:10.1145/321752.321754
[89] DOI: 10.1007/BF02579369 · Zbl 0596.90030 · doi:10.1007/BF02579369
[90] DOI: 10.1287/moor.16.2.272 · Zbl 0743.90108 · doi:10.1287/moor.16.2.272
[91] Tarjan R., Math. Program 78 pp 169– (1997)
[92] DOI: 10.1002/net.3230010206 · Zbl 0253.90015 · doi:10.1002/net.3230010206
[93] DOI: 10.1145/335305.335319 · Zbl 1296.90017 · doi:10.1145/335305.335319
[94] DOI: 10.1007/s001860200202 · Zbl 1023.90074 · doi:10.1007/s001860200202
[95] DOI: 10.1287/mnsc.21.1.87 · Zbl 0319.90064 · doi:10.1287/mnsc.21.1.87
[96] Yakovleva M., Applications of Mathematics in Economic Research pp 390– (1959)
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.