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

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.