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

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.


90B10 Deterministic network models in operations research
Full Text: DOI


[1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flow: theory, algorithms, and applications, (1993), 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)
[8] A.J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, in: R. Bellman, M. Hall Jr., (Eds.), Proceedings of the Symposia in Applied Mathematics, vol. X Combinatorial Analysis, American Mathematical Society, Providence RI, 1960, pp. 113-127.
[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
[11] S. Phillips, J. Westbrook, Online load balancing and network flow, in: Proc. 25th Ann. ACM Symposium on Theory of Comput., 1993, pp. 402-411. · Zbl 1310.90019
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.