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

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

0.00 Avg rating0 Votes
Article ID: iaor20083373
Country: Netherlands
Volume: 192
Issue: 2
Start Page Number: 429
End Page Number: 438
Publication Date: Oct 2007
Journal: Applied Mathematics and Computation
Authors: ,
Keywords: programming: network
Abstract:

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

Reviews

Required fields are marked *. Your email address will not be published.