×

Minimal-cost network flow problems with variable lower bounds on arc flows. (English) Zbl 1208.90031

Summary: The minimal-cost network flow problem with fixed lower and upper bounds on arc flows has been well studied. This paper investigates an important extension, in which some or all arcs have variable lower bounds. In particular, an arc with a variable lower bound is allowed to be either closed (i.e., then having zero flow) or open (i.e., then having flow between the given positive lower bound and an upper bound). This distinctive feature makes the new problem NP-hard, although its formulation becomes more broadly applicable, since there are many cases where a flow distribution channel may be closed if the flow on the arc is not enough to justify its operation. This paper formulates the new model, referred to as MCNF-VLB, as a mixed integer linear programming, and shows its NP-hard complexity. Furthermore, a numerical example is used to illustrate the formulation and its applicability. This paper also shows a comprehensive computational testing on using CPLEX to solve the MCNF-VLB instances of up to medium-to-large size.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
90C11 Mixed integer programming

Software:

RELAX4; CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertsekas, D. P.; Tseng, P., Relaxation methods for minimum cost ordinary and generalized network flow problems, Oper Res, 36, 1, 93-114 (1988) · Zbl 0662.90027
[2] Wayne KD. A polynomial combinatorial algorithm for generalized minimum cost flow. In: Proceedings of the 31st annual ACM symposium on theory of computing, 1999. p. 11-8.; Wayne KD. A polynomial combinatorial algorithm for generalized minimum cost flow. In: Proceedings of the 31st annual ACM symposium on theory of computing, 1999. p. 11-8.
[3] Orlin JB. A faster strongly polynomial minimum cost flow algorithm. In: Proceedings of the 20th annual ACM symposium on theory of computing, 1988. p. 377-87.; Orlin JB. A faster strongly polynomial minimum cost flow algorithm. In: Proceedings of the 20th annual ACM symposium on theory of computing, 1988. p. 377-87.
[4] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows: theory, algorithms, and applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[5] Klein, M., A primal method for minimum cost flows, with applications to the assignment and transportation problems, Manage Sci, 14, 205-220 (1967) · Zbl 0178.22902
[6] Iri, M., A new method for solving transportation-network problems, J Oper Res Soc Jpn, 3, 27-87 (1960)
[7] Ford, L. R.; Fulkerson, D. R., A primal-dual algorithm for the capacitated Hitchcock problem, Nav Res Logist Q, 4, 47-54 (1957) · Zbl 0143.42401
[8] Ford, L. R.; Fulkerson, D. R., Flows in networks (1962), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0139.13701
[9] Fulkerson, D. R., An Out-of-Kilter method for minimal cost flow problems, SIAM J Appl Math, 9, 18-27 (1961) · Zbl 0112.12401
[10] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, J ACM, 19, 248-264 (1972) · Zbl 0318.90024
[11] Röck, H., Scaling techniques for minimal cost network flows, (Page, V., Discrete structures and algorithms (1980), Carl Hanser: Carl Hanser Munich), 181-191
[12] Ahuja, R. K.; Goldberg, A. V.; Orlin, J. B.; Tarjan, R. E., Finding minimum-cost flows by double scaling, Math Program, 53, 3, 243-266 (1992) · Zbl 0761.90036
[13] Goldberg AV, Tarjan RE. Finding minimum-cost circulations by canceling negative cycles. MIT/LCS/TM-334, 1987, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA.; Goldberg AV, Tarjan RE. Finding minimum-cost circulations by canceling negative cycles. MIT/LCS/TM-334, 1987, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA.
[14] Goldberg AV, Tardos E, Tarjan R. Network flow algorithm. Technical report 860. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1989.; Goldberg AV, Tardos E, Tarjan R. Network flow algorithm. Technical report 860. School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1989.
[15] Phillips, D. T.; Garcia-Diaz, A., Fundamentals of network analysis. International series in industrial and systems engineering (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[16] Dantzig GB. Application of the simplex method to a transportation problem. Activity analysis of production and allocation. Cowles Commission Monograph 13, 1951.; Dantzig GB. Application of the simplex method to a transportation problem. Activity analysis of production and allocation. Cowles Commission Monograph 13, 1951.
[17] Johnson, E., Networks and basic solutions, Oper Res, 14, 619-623 (1966)
[18] Bazaraa, M. S.; Jarvis, J. J., Linear programming and network flows (1977), Wiley: Wiley New York · Zbl 1060.90688
[19] Kennington, J. L.; Helgason, R. V., Algorithms for network programming (1980), Wiley: Wiley New York · Zbl 0502.90056
[20] Bradley, G. H.; Brown, G. G.; Graves, G. W., Design and implementation of large scale primal transshipment algorithms, Manage Sci, 24, 1, 1-34 (1977) · Zbl 0373.90079
[21] Mulvey, J. J., Pivot strategies for primal-simplex network codes, J ACM, 25, 2, 266-270 (1978) · Zbl 0379.90101
[22] Ahuja, R. K.; Hochbaum, D. S.; Orlin, J. B., Solving the convex cost integer dual network flow problem, Manage Sci, 49, 7, 950-964 (2003) · Zbl 1232.90317
[23] Orlin, J. B., Minimum convex cost dynamic network flows, Math Oper Res, 9, 2, 190-207 (1984) · Zbl 0568.90028
[24] Weintraub, A., A primal algorithm to solve network flow problems with convex costs, Manage Sci, 21, 1, 87-97 (1974) · Zbl 0319.90064
[25] Amiri, A.; Pirkul, H., New formulation and relaxation to solve a concave-cost network flow problem, J Oper Res Soc, 48, 3, 278-297 (1997) · Zbl 0890.90060
[26] Erickson, R. E.; Monma, C. L.; Veinott, A. F., Send-and-split method for minimum-concave-cost network flows, Math Oper Res, 12, 4, 634-664 (1987) · Zbl 0667.90036
[27] Monma, C. L.; Segal, M., A primal algorithm for finding minimum-cost flows in capacitated networks with applications, Bell Syst Tech J, 61, 949-968 (1982)
[28] Magnanti, T. L.; Wong, R. T., Network design and transportation planning: models and algorithms, Transport Sci, 18, 1-55 (1983)
[29] Zangwill, W. I., Minimum concave cost flows in certain networks, Manage Sci, 14, 7, 429-450 (1968) · Zbl 0159.49102
[30] Connors, M. M.; Zangwill, W. I., Cost minimization in networks with discrete stochastic requirements, Oper Res, 19, 3, 794-821 (1970) · Zbl 0219.90015
[31] Figueira, J.; Silti, H. M.; Tolla, P., Using mathematical programming heuristics in a multicriteria network flow context, J Oper Res Soc, 49, 878-885 (1998) · Zbl 1140.90337
[32] Ghatee, M.; Hashemi, S. M., Application of fuzzy minimum cost flow problems to network design under uncertainty, Fuzzy Set Syst, 160, 22, 3263-3289 (2009) · Zbl 1176.90674
[33] Shih, H.-S.; Lee, E. S., Fuzzy multi-level minimum cost flow problems, Fuzzy Set Syst, 107, 2, 159-176 (1999) · Zbl 0953.90060
[34] Geunes, J.; Pardalos, P. M., Supply chain optimization (2005), Springer: Springer Berlin · Zbl 1078.90002
[35] Cabot, A. V.; Erenguc, S. S., Some branch and bound procedures for fixed-cost transportation problems, Nav Res Logist Q, 31, 145-154 (1984) · Zbl 0537.90074
[36] Palekar, U. S.; Karwan, M. H.; Zionts, S., A branch-and-bound method for the fixed charge transportation problem, Manage Sci, 36, 9, 1092-1105 (1990) · Zbl 0718.90068
[37] Ortega, F.; Wolsey, L. A., A branch-and-cut algorithm for the single-commodity, uncapacitated fixed-charge network flow problem, Networks, 41, 3, 143-158 (2003) · Zbl 1106.90016
[38] Cruz, F. R.B.; Smith, J. M.; Mateus, G. R., Solving to optimality the uncapacitated fixed-charge network flow problem, Comput Oper Res, 25, 1, 67-81 (1998) · Zbl 0907.90132
[39] Costa, A. M., A survey on benders decomposition applied to fixed-charge network design problems, Comput Oper Res, 32, 6, 1429-1450 (2005) · Zbl 1071.90009
[40] Sun, M.; McKeown, P. G., Tabu search applied to the general fixed charge problem, Ann Oper Res, 41, 1-4, 405-420 (1993) · Zbl 0775.90287
[41] Walker, W. E., A heuristic adjacent extreme point algorithm for the fixed charge problem, Manage Sci, 22, 5, 587-596 (1976) · Zbl 0316.90041
[42] Garcia-Diaz A, Kim SB, Sawhney R. Optimal procedures for minimizing commodity distribution costs in networks with conditional arc lower bounds. In: Proceedings of the 2008 industrial engineering research conference, 2008. Paper no. 285.; Garcia-Diaz A, Kim SB, Sawhney R. Optimal procedures for minimizing commodity distribution costs in networks with conditional arc lower bounds. In: Proceedings of the 2008 industrial engineering research conference, 2008. Paper no. 285.
[43] Kim S. A network transformation procedure for finding minimal-cost flows in networks with variable lower bounds. Thesis (MS), INEN Department, Texas A&M University, College Station, TX, 1991.; Kim S. A network transformation procedure for finding minimal-cost flows in networks with variable lower bounds. Thesis (MS), INEN Department, Texas A&M University, College Station, TX, 1991.
[44] ILOG. ILOG CPLEX 11.0 user’s manual, 2007.; ILOG. ILOG CPLEX 11.0 user’s manual, 2007.
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.