A new algorithm for solving the feasibility problem of a network flow. (English) Zbl 1193.90049

Fathabadi, Hassan Salehi; Ghiyasvand, Mehdi

Appl. Math. Comput. 192, No. 2, 429-438 (2007).

Summary: A network \(D\) with the constraints of conservation and boundedness is given. The feasibility problem is defined as: Is there a flow x satisfying the constraints? In this paper we suppose that the lower and upper bounds are integers. We first present a new theorem characterizing the conditions for feasibility and then describe a scaling algorithm to solve the problem. Our algorithm relaxes the capacity bounds and then successively reduces the value of relaxation. If the network is infeasible then our algorithm not only diagnoses it and finds a positive cut but also gives a geometrical description to feasibility concept. Our algorithm also helps modeler to repair an infeasible network or to estimate the maximum cost of repairing. For a network with \(n\) nodes and \(m\) arcs, the algorithm runs in \(O(m^{2}\log (nU))\) time, where \(U\) is the largest absolute arc bounds.

MSC:

90B10

Deterministic network models in operations research

Keywords:

operation research; network flow; infeasible network; scaling algorithm; positive cut

References:

[1]	Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network Flow: Theory, Algorithms, and Applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2]	Ahuja, R. K.; Orlin, J. B.; Tarjan, R. E., Improved time bounds for the maximum flow problem, SIAM J. Comput., 18, 939-954 (1989) · Zbl 0675.90029
[3]	Ghiyasvand, M., A new approach for computing a most positive cut using the minimum flow algorithms, Appl. Math. Comput., 176, 27-36 (2006) · Zbl 1098.65062
[4]	Goldberg, A. V.; Rao, S., Beyond the flow decomposition barrier, J. ACM, 45, 735-797 (1988) · Zbl 1064.90567
[5]	Goldberg, A. V.; Tarjan, R. E., A new approach to the maximum flow problem, J. ACM, 35, 921-940 (1998) · Zbl 0661.90031
[6]	Hassin, R., The minimum cost flow problem: a unifying approach to dual algorithms and a new tree-search algorithm, Math. Program., 25, 228-239 (1983) · Zbl 0501.90035
[7]	Hassin, R., Algorithm for the minimum cost circulation problem based on maximizing the mean improvement, Oper. Res. Lett., 12, 228-239 (1992)
[9]	King, v.; Rao, S.; Tarjan, R., A faster deterministic maximum flow algorithm, J. Algorithms, 17, 447-474 (1994) · Zbl 1321.05269
[10]	McCormick, S. T.; Ervolina, T. R., Computing maximum mean cuts, Discret. Appl. Math., 52, 53-70 (1994) · Zbl 0824.90058