Algorithms for the simple equal flow problem

Algorithms for the simple equal flow problem

0.00 Avg rating0 Votes
Article ID: iaor20002350
Country: United States
Volume: 45
Issue: 10
Start Page Number: 1440
End Page Number: 1455
Publication Date: Oct 1999
Journal: Management Science
Authors: , , ,
Keywords: programming: network, programming: parametric
Abstract:

The minimum cost flow problem is to determine a least cost shipment of a commodity through a network G = (N, A) in order to satisfy demands at certain nodes from available supplies at other nodes. In this paper, we study a variant of the minimum cost flow problem where we are given a set RA of arcs and require that each arc in R must carry the same amount of flow. This problem, which we call the simple equal flow problem, arose while modeling a water resource system management in Sardinia, Italy. We consider the simple equal flow problem in a directed network with n nodes, m arcs, and where all arc capacities and node supplies are integer and bounded by U. We develop several algorithms for the simple equal flow problem – the network simplex algorithm, the parametric simplex algorithm, the combinatorial parametric algorithm, the binary search algorithm, and the capacity scaling algorithm. The binary search algorithm solves the simple equal flow problem in O(log(nU)) applications of any minimum cost flow algorithm. The capacity scaling algorithm solves it in O(m(m+n log n) log (nU)) time, which is almost the same time, needed to solve the minimum cost flow problem by the capacity scaling algorithm. These algorithms can be easily modified to obtain an integer solution of the simple equal flow problem.

Reviews

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