|
Description: |
We consider the Single Source Uncapacitated (SSU) Minimum Cost Network Flow Problem (MCNFP) with general concave costs, in which a subset of arcs must be selected so that flow can be routed to vertices with known demands from a single source at minimum cost.
A Dynamic Programming methodology for solving optimally the SSU concave MCNFP is presented. The DP approach presented is independent of the type of arcs cost functions as well as of the number of arcs with nonlinear costs. The only two requirements are separability and additivity of the cost function.
Lower Bounds can be derived from state space relaxations of this formulation, which involve the use of non-injective mapping functions guaranteing a reduction on the cardinality of the state space.
Area(s):
|
