Minimum cost network flows: Problems, algorithms, and software
DOI:
https://doi.org/10.2298/YJOR121120001SKeywords:
Mathematical Programming, Combinatorial Optimization, Optimization SoftwareAbstract
We present a wide range of problems concerning minimum cost network flows, and give an overview of the classic linear single-commodity Minimum Cost Network Flow Problem (MCNFP) and some other closely related problems, either tractable or intractable. We also discuss state-of-the-art algorithmic approaches and recent advances in the solution methods for the MCNFP. Finally, optimization software packages for the MCNFP are presented.References
Ahuja, R.K., Goldberg, A.V., Orlin, J.B., and Tarjan, R.E., “Finding minimum – cost flows by double scaling”, Mathematical Programming, 53 (3) (1992) 243–266.
Ahuja, R.K., Magnanti, T.L., and Orlin, J.B., Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.
Ahuja, R.K., and Orlin, J.B., “The scaling network simplex algorithm”, Operations Research, 40 (S1) (1992) 5–13.
Andreou, D., Paparrizos, K., Samaras, N., and Sifaleras, A., “Application of a new network – enabled solver for the assignment problem in computer – aided education”, Journal of Computer Science, 1 (1) (2005) 19–23.
Andreou, D., Paparrizos, K., Samaras, N., and Sifaleras, A., “Visualization of the network exterior primal simplex algorithm for the minimum cost network flow problem”, Operational Research, 7 (3) (2007) 449–464.
Arthur, J.L., and Frendewey, J.O., “An algorithm for generating minimum cost network flow problems with specific structure and known optimal solutions”, Networks, 24 (8) (1994) 445-454.
Badr, E.S., Moussa, M., Paparrizos, K., Samaras, N., and Sifaleras, A., “Some computational results on MPI parallel implementation of dense simplex method”, in: Proc. of World Academy of Science, Engineering and Technology, 23 (2006) 39–42.
Baloukas, Th., Paparrizos, K., and Sifaleras, A., “An animated demonstration of the uncapacitated network simplex algorithm”, INFORMS Transactions on Education, 10 (1) (2009) 34–40.
Barr, R.S., Glover, F., and Klingman, D., “Enhancements to spanning tree labeling procedures for network optimization”, INFOR, 17 (1979) 16–34.
Barr, R.S., and Hickman, B.L., “Parallel simplex for large pure network problems: computational testing and sources of speedup”, Operations Research, 42 (1) (1994) 65–80.
Basten, R.J.I., Heijden, M.C., and Schutten, J.M.J., “A minimum cost flow model for level of repair analysis”, International Journal of Production Economics, 133 (1) (2011) 233–242.
Basten, R.J.I., Heijden, M.C., and Schutten, J.M.J., “Practical extensions to a minimum cost flow model for level of repair analysis”, European Journal of Operational Research, 211 (2) (2011) 333–342.
Bazaraa, M.S., Jarvis, J.J., and Sherali, H.D., Linear Programming and Network Flows, 4th Ed., John Wiley and Sons, Inc, 2009.
Beraldi, P., Guerriero, F., and Musmanno, R., “Efficient parallel algorithms for the minimum cost flow problem”, Journal of Optimization Theory and Applications, 95 (3) (1997) 501–530.
Beraldi, P., Guerriero, F., and Musmanno, R., “Parallel algorithms for solving the convex minimum cost flow problem”, Computational Optimization and Applications, 18 (2) (2001) 175–190.
Bertsekas, D.P., and Tseng, P., “RELAX-IV: A faster version of the RELAX code for solving minimum cost flow problems”, Technical Report P-2276, Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, 1994.
Bixby, R.E., “Mixed-integer programming: It works better than you may think. Gurobi optimization”, FERC Conference, Washington, DC, June 9, 2010.
Burkard, R., Dell'Amico, M., and Martello, S., Assignment Problems – Revised Reprint, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2012.
Cai, X., Sha, D., and Wong, C.K., “Time-varying minimum cost flow problems”, European Journal of Operational Research, 131 (2) (2001) 352–374.
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). “The first DIMACS international algorithm implementation challenge: Problem definitions and specifications”, Technical report, DIMACS, New Brunswick, NJ, 1991.
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), “The first DIMACS international algorithm implementation challenge: The benchmark experiments”, Technical report, DIMACS, New Brunswick, NJ, 1991.
Cunningham, W.H., “A network simplex method”, Mathematical Programming, 11 (1) (1976) 105–116.
Daneshpajouh, H., and Alimomeni, M., “A note on the minimum interval cost flow problem”, Applied Mathematics and Computation, 217 (17) (2011) 7051–7052.
Dezső, B., Jüttner, A., and Kovács, P., “LEMON – an open source C++ graph template library”, Electronic Notes in Theoretical Computer Science, 264 (5) (2011) 23–45.
Du, D.Z., and Pardalos, P.M., (Eds.), Network Optimization Problems: Algorithms, Applications and Complexity, In: Series on Applied Mathematics, 2, World Scientific, Singapore, 1993.
Ebrahim, R.M., and Razmi, J., “A hybrid metaheuristic algorithm for bi-objective minimum cost flow (BMCF) problem”, Advances in Engineering Software, 40 (10) (2009) 1056–1062.
Edmonds, J., and Giles, R., “A min-max relation for submodular functions on graphs”, Annals of Discrete Mathematics, 1 (1977) 185–204.
Edmonds, J., and Karp, R.M., “Theoretical improvements in algorithmic efficiency for network flow problems”, Journal of the ACM, 19 (2) (1972) 248–264.
Eom, S., and Kim, E., “A survey of decision support system applications (1995–2001)”, Journal of the Operational Research Society, 57 (11) (2006) 1264–1278.
Even, S., Itai, A., and Shamir, A., “On the complexity of timetable and multicommodity flow problems”, SIAM Journal on Computing, 5 (4) (1976) 691–703.
Ferris, M.C., Mesnier, M.P., and Moré, J.J., “NEOS and Condor: solving optimization problems over the Internet”, ACM Transactions on Mathematical Software, 26 (1) (2000) 1–18.
Fontes, D.B., Hadjiconstantinou, E., and Christofides, N., “A dynamic programming approach for solving single-source uncapacitated concave minimum cost network flow problems”, European Journal of Operational Research, 174 (2) (2006) 1205–1219.
Fontes, D.B., Hadjiconstantinou, E., and Christofides, N., “A branch-and-bound algorithm for concave network flow problems”, Journal of Global Optimization, 34 (1) (2006) 127–155.
Frangioni, A., and Manca, A., “A computational study of cost reoptimization for min-cost flow problems”, INFORMS Journal on Computing, 18 (1) (2006) 61–70.
Fredman, M.L., and Tarjan, R.E., “Fibonacci heaps and their uses in improved network optimization algorithms”, Journal of the ACM, 34 (3) (1987) 596–615.
Gabow, H.N., and Tarjan, R.E., “Faster scaling algorithms for network problems”, SIAM Journal on Computing, 18 (5) (1989) 1013–1036.
Gamarnik, D., Shah, D., and Wei, Y., “Belief propagation for min-cost network flow: convergence and correctness”, Operations Research, 60 (2) (2012) 410–428.
Geranis, G., Paparrizos, K., and Sifaleras, A., “A dual exterior point simplex type algorithm for the minimum cost network flow problem”, Yugoslav Journal of Operations Research, 19 (1) (2009) 157–170.
Geranis, G., Paparrizos, K., and Sifaleras, A., “On a dual network exterior point simplex type algorithm and its computational behavior”, RAIRO - Operations Research, 46 (3) (2012) 211–234.
Ghatee, M., and Hashemi, S.M., “Generalized minimal cost flow problem in fuzzy nature: An application in bus network planning problem”, Applied Mathematical Modelling, 32 (12) (2008) 2490–2508.
Ghatee, M., and Hashemi, S.M., “Application of fuzzy minimum cost flow problems to network design under uncertainty”, Fuzzy Sets and Systems, 160 (22) (2009) 3263–3289.
Ghatee, M., Hashemi, S.M., Zarepisheh, M., and Khorram, E., “Preemptive priority-based algorithms for fuzzy minimal cost flow problem: An application in hazardous materials transportation”, Computers & Industrial Engineering, 57 (1) (2009) 341–354.
Goldberg, A.V., “An efficient implementation of a scaling minimum-cost flow algorithm”, Journal of Algorithms, 22 (1) (1997) 1–29.
Goldfarb, D., and Jin, Z., “A new scaling algorithm for the minimum cost network flow problem”, Operations Research Letters, 25 (5) (1999) 205–211.
Gopalakrishnan, B., Kong, S., Barnes, E., Johnson, E.L., and Sokol, J.S., “A least-squares minimum-cost network flow algorithm”, Annals of Operations Research, 186 (1) (2011) 119–140.
Grigoriadis, M., “An efficient implementation of the network simplex method”, Mathematical Programming Studies, 26 (1984) 83–111.
Guisewite, G.M., and Pardalos, P.M., “Minimum concave-cost network flow problems: applications, complexity, and algorithms”, Annals of Operations Research 25 (1) (1991) 75–100.
Güler, Ç., and Hamacher, H.W., “Capacity inverse minimum cost flow problem”, Journal of Combinatorial Optimization, 19 (1) (2010) 43–59.
Hamacher, H.W., Pedersen, C.R., and Ruzika, S., “Multiple objective minimum cost flow problems: A review”, European Journal of Operational Research, 176 (3) (2007) 1404–1422.
Haro, D., Paredes, J., Solera, A., and Andreu, J., “A model for solving the optimal water allocation problem in river basins with network flow programming when introducing non-linearities”, Water Resources Management, 26 (14) (2012) 4059–4071.
Hashemi, S.M., Ghatee, M., and Nasrabadi, E., “Combinatorial algorithms for the minimum interval cost flow problem”, Applied Mathematics and Computation, 175 (2) (2006) 1200–1216.
International Business Machines Corporation (IBM), “V12.1 User’s Manual for CPLEX”, 2009.
Jiang, Y., Liu, L., Wu, B., and Yao, E., “Inverse minimum cost flow problems under the weighted Hamming distance”, European Journal of Operational Research, 207 (1) (2010) 50–54.
Kennington, J., and Helgason, R., Algorithms for Network Programming, Wiley, New York, 1980.
Király, Z., and Kovács, P., “Efficient implementations of minimum-cost flow algorithms”, Acta Universitatis Sapientiae, Informatica, 4 (1) (2012) 67–118.
Klingman, D., Napier, A., and Stutz, J., “NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow networks”, Management Science, 20 (5) (1974) 814–821.
Korte, B., and Vygen, J., Combinatorial Optimization, Theory and Algorithms, (5th ed.). In Series: Algorithms and Combinatorics, 21, Springer-Verlag, Bonn, 2012.
Krumke, S.O., and Thielen, C., “Minimum cost flows with minimum quantities”, Information Processing Letters, 111 (11) (2011) 533–537.
Lazaridis, V., Samaras, N., and Sifaleras, A., “An empirical study on factors influencing the effectiveness of algorithm visualization”, accepted for publication in Computer Applications in Engineering Education, (2010).
Lee, Y., and Orlin, J.B., “Computational testing of a network simplex algorithm”, in: Proc. of the 1st DIMACS International Algorithm Implementation Challenge, (1991).
Löbel, A., “Solving large-scale real-world minimum-cost flow problems by a network simplex method”, Technical report SC 96-7, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, Germany, 1996.
Mehlhorn, K., and Näher, S., LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, Boston 1999.
Migdalas, A., Sifaleras, A., Georgiadis, C.K., Papathanasiou, J., and Stiakakis, E., eds., Optimization Theory, Decision Making, and Operations Research Applications. In Series: Springer Proceedings in Mathematics & Statistics, 31, Springer, New York, USA, 2013.
Minoux, M., “Solving integer minimum cost flows with separable convex cost objective polynomially”, Mathematical Programming Studies, 26 (1986) 237–239.
Nasrabadi, E., and Hashemi, S.M., “Minimum cost time-varying network flow problems”, Optimization Methods and Software, 25 (3) (2010) 429–447.
Oliveira, C.A.S, and Pardalos, P.M., Mathematical Aspects of Network Routing Optimization, 53. In Series: Springer Optimization and Its Applications, Springer, New York, USA, 2011.
Orlin, J.B., “A faster strongly polynomial minimum cost flow algorithm”, Operations Research, 41 (2) (1993) 338–350.
Orlin, J.B., “A polynomial time primal network simplex algorithm for minimum cost flows”, Mathematical Programming, 78 (2) (1997) 109–129.
Orlin, J.B., and Stein, C., “Parallel algorithms for the assignment and minimum-cost flow problems”, Operations Research Letters, 14 (4) (1993) 181–186.
Papamanthou, Ch., Paparrizos, K., Samaras, N., and Sifaleras, A., “On the initialization methods of an exterior point algorithm for the assignment problem”, International Journal of Computer Mathematics, 87 (8) (2010) 1831–1846.
Paparrizos, K., Samaras, N., and Sifaleras, A., “An exterior Simplex type algorithm for the minimum cost network flow problem”, Computers & Operations Research, 36 (4) (2009) 1176–1190.
Pardalos, P.M., Hearn, D.W., and Hager, W.W., eds., Network Optimization, Lecture Notes in Economics and Mathematical Systems, 450, Springer, Germany, 1997.
Pardalos, P.M., Du, D.Z., and Graham, R.L., eds., Handbook of Combinatorial Optimization, 2nd ed., 2013.
Peters, J., “The network simplex method on a multiprocessor”, Networks, 20 (7) (1990) 845–859.
Portugal, L., Resende, M., Veiga, G., Patrício, J., and Júdice, J., “Fortran subroutines for network flow optimization using an interior point algorithm”, Pesquisa Operacional, 28 (2) (2008) 243–261.
Rakshit, A., Krishnamurthy, N., and Yu, G., “System operations advisor: A real-time decision support system for managing airline operations at United Airlines”, Interfaces, 26 (2) (1996) 50–58.
Resende, M.G.C., and Pardalos, P.M., “Interior point algorithms for network flow problems”, in J.E. Beasley, ed., Advances in linear and integer programming, Oxford University Press, (1996) 147–187.
Resende, M.G.C., and Veiga, G., “An efficient implementation of a network interior point method”, in: D.S. Johnson and C.C. McGeoch, eds., Network flows and matching: First DIMACS implementation challenge, 12, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, Rhode Island, (1993) 299–348.
Samaras, N., Sifaleras, A., and Triantafyllidis, C., “A primal–dual exterior point algorithm for linear programming problems”, Yugoslav Journal of Operations Research, 19 (1) (2009) 123–132.
SAS Institute Inc., “SAS/OR ® 9.22 User’s Guide: Mathematical Programming”, Cary, NC, (2010).
Sedeño-Noda, C., “The biobjective minimum cost flow problem”, European Journal of Operational Research, 124 (3) (2000) 591–600.
Sedeño-Noda, A., and C., “An algorithm for the biobjective integer minimum cost flow problem”, Computers & Operations Research, 28 (2) (2001) 139–156.
Sedeño-Noda, A., C., and Gutiérrez, J., “The biobjective undirected two-commodity minimum cost flow problem”, European Journal of Operational Research, 164 (1) (2005) 89–103.
Shih, H.-S., and Lee, E.S., “Fuzzy multi-level minimum cost flow problems”, Fuzzy Sets and Systems, 107 (2) (1999) 159–176.
Sleator, D.D., and Tarjan, R.E., “A data structure for dynamic trees”, Journal of Computer and System Sciences, 26 (3) (1983) 362–391.
Tardos, E., “A strongly polynomial minimum cost circulation algorithm”, Combinatorica, 5 (3) (1985) 247–255.
Thai, M.T., and Pardalos, P.M., (Eds.), Handbook of Optimization in Complex Networks, 57-58. In Series: Springer Optimization and Its Applications, New York, USA, 2012.
Thibault, E., “A decision support system for the design of cost-effective metropolitan area networks”, Thesis Report, University of Ottawa, 1999.
Thulasiraman, K., Chalasani, R.P., and Comeau, M.A., “Parallel network dual simplex method on a shared memory multiprocessor”, in: Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing, Dallas, TX, 1993, 408–415.
Tuy, H., Ghannadana, S., Migdalas, A., and Värbrand, P., “Strongly polynomial algorithm for two special minimum concave cost network flow problems”, Optimization: A Journal of Mathematical Programming and Operations Research, 32 (1) (1995) 23–43.
Vaidyanathan, B., and Ahuja, R.K., “Fast algorithms for specially structured minimum cost flow problems with applications”, Operations Research, 58 (6) (2010) 1681–1696.
Végh, L.A., “Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives”, in: Proceedings of the 44th symposium on Theory of Computing (STOC '12), ACM, New York, USA, 2012, 27–40.
Voudouris, K., Polemio, M., Kazakis, N., and Sifaleras, A., “An agricultural decision support system for optimal land use regarding groundwater vulnerability”, International Journal of Information Systems and Social Change, 1 (4) (2010) 66–79.
Vygen, J., “On dual minimum cost flow algorithms”, Mathematical Methods of Operations Research, 56 (1) (2002) 101–126.
Wayne, K.D., “A Polynomial combinatorial algorithm for generalized minimum cost flow”, Mathematics of Operations Research, 27 (3) (2002) 445–459.
Xu, J., Tu, Y., and Zeng, Z., “A nonlinear multiobjective bilevel model for minimum cost network flow problem in a large-scale construction project”, Mathematical Problems in Engineering, (2012), Article ID 463976.
Xu, C., Xu, X.-M., and Wang, H.-F., “The fractional minimal cost flow problem on network”, Optimization Letters, 5 (2) (2011) 307–317.
Zhu, X., Yuan, Q., Garcia-Diaz, A., and Dong, L., “Minimal-cost network flow problems with variable lower bounds on arc flows”, Computers & Operations Research, 38 (8) (2011) 1210–1218.
Downloads
Published
Issue
Section
License
Copyright (c) 2013 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
