Minimum-Cost Flows in Networks with Upper Bounded Arcs and Concave Cost Functions
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1972
- Accession Number
- AD0758504
Entities
People
- Wayne J. Hallenbeck Jr.
Organizations
- Naval Postgraduate School