New Methods in Mathematical Programming---Optimal Flow Through Networks with Gains

William S. Jewell
Additional contact information
William S. Jewell: University of California, Berkeley, California

Operations Research, 1962, vol. 10, issue 4, 476-499

Abstract: The special class of linear programs described as network flow problems includes many of the special structure optimization problems in such areas as assignment, transportation, catering, warehousing, production scheduling, etc. Besides the physical motivation of the flow description, this class of problems possesses conceptually simple, and computationally elegant, solution techniques originated by Dantzig, Ford, Fulkerson, et al. This paper describes a generalization of this class of problems to “process-flow networks,” or “flow with gains,” in which flow in any branches of the network may be multiplied by an arbitrary constant, called the branch gain, before leaving the branch and flowing into the remainder of the network. This generalization permits the description of networks in which different kinds of flow may be converted one to another, without “constant returns to scale.” Among other interesting problems, this model includes the metal-processing problem, the machine-loading problem, financial budgeting, aircraft routing, warehousing with “breeding” or “evaporation,” the two-equation capacitated linear program, etc. The solution method here described and proved is a natural extension of Ford and Fulkerson's technique (or specialization of the primal-dual method) and retains much of the physical motivation and easy computational aspect of their technique, a direct starting solution is usually available, and optimization of the imbedded linear program (the restricted primal problem) can be accomplished without the use of the simplex technique. Conceptually, the solution procedure consists of the following steps Find the incrementally cheapest loop in the network that will absorb flow Establish as much additional flow into the network along this route as possible Repeat Steps (1) and (2) until the desired flow is established, or until infeasibility is discovered The solution technique includes a maximal-flow procedure and produces a “min-cut equals max-flow” theorem for networks with gains. Additional features, such as piece-wise linear convex costs, parametric studies, network “tearing,” mixed boundary conditions, etc., may be easily incorporated in the algorithm.

Date: 1962
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.10.4.476 (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:oropre:v:10:y:1962:i:4:p:476-499

Access Statistics for this article

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