A new algorithm for solving the feasibility problem of a network flow

摘要

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(m2log(nU)) time, where U is the largest absolute arc bounds.