Optimal Flow In A Network With Gains^*

* This paper is part of a Yale University doctoral dissertation. The author wishes to thank Professors Harvey M. Wagner and Eric V. Denardo for their assistance with this research.

Abstract

Consider a capacitated network in which the flow leaving an arc equals the flow entering that arc multiplied by a constant. Jewell has presented an algorithm to construct a minimal cost flow for the network when the net flow out of each node is specified. This algorithm is difficult to initialize and need not terminate finitely.

This paper shows how to (1) initialize Jewell’s algorithm without difficulty, (2) modify Jewell’s algorithm to ensure its finite convergence, and (3) interpret Jewell’s algorithm as an out-of-kilter algorithm.

Résumé

Considérons un réseau avec des capacités telles que le flux sortant d’un arc est égal au flux entrant cet arc, multiplié par une facteur. W.S. Jewell a publié un algorithme pour construire, aà coût minimal, un flot pour le réseau lorsque le flot net sortant de chaque noeud est donné. II est difficile de trouver des conditions initiates pour cet algorithme, de plus il ne converge pas de manifère finie.

Cet article montre (1) comment trouver sans difficultés, les conditions initiales de l’algorithme de Jewell, (2) comment modifier l’algorithme de Jewell pour s’assurer de sa convergence finie, (3) que l’algorithme de Jewell est un algorithme “out-of-kilter.”

Notes

* This paper is part of a Yale University doctoral dissertation. The author wishes to thank Professors Harvey M. Wagner and Eric V. Denardo for their assistance with this research.

Additional information

Notes on contributors

Edward Minieka

EDWARD MINIEKA is an alumnus of the Illinois Institute of Technology, Stanford University, and Yale University, where he received his doctorate. He has been a research fellow at the Center for Operations Research and Econometrics of the University of Louvain, Belgium, and at the Department of Mathematics, Dalhousie University, Halifax, Canada. Currently, he is a visiting professor in the Department of Statistics, Trinity College, Dublin, Ireland. His current research interests include graph theoretic optimization problems and matroid theory. Currently, he is preparing the English edition of Graphes et Hypergraphes by Claude Berge.