Minimum-Cost Flows in Networks with Upper Bounded Arcs and Concave Cost Functions
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
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.
- Operations Research