Algorithms for the Simple Equal Flow Problem

Ravindra K. Ahuja, James B. Orlin, Giovanni M. Sechi and Paola Zuddas
Additional contact information
Ravindra K. Ahuja: Department of Industrial & Systems Engineering, University of Florida, Gainesville, Florida 32611
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Giovanni M. Sechi: Department of Hydraulics, University of Cagliari, 09123 Cagliari, Sardinia, Italy
Paola Zuddas: Department of Hydraulics, University of Cagliari, 09123 Cagliari, Sardinia, Italy

Management Science, 1999, vol. 45, issue 10, 1440-1455

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 R \subseteq A 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 logn) 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.

Keywords: minimum cost flow problem; network simplex algorithm; scaling algorithm; parametric programming; network flows (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.45.10.1440 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:45:y:1999:i:10:p:1440-1455

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().