Accession Number:

AD0758504

Title:

Minimum-Cost Flows in Networks with Upper Bounded Arcs and Concave Cost Functions

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s):

Report Date:

1972-12-01

Pagination or Media Count:

34.0

Abstract:

An algorithm is presented for solving minimum-cost flow problems in which each arc of the network has a finite maximum flow capacity and a concave cost function associated with sending flow along that arc. Each cost function is broken into a series of cost increments through the use of piecewise linear approximations. The algorithm takes any feasible solution and recirculates flow over less costly cycles to obtain an optimal solution. A modification which handles the existence of non-zero lower bounds on flow through the various arcs is also given.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE