Tuesday, 13:15 - 13:40 h, Room: H 2032


Qie He
Minimum concave cost network flow over a grid network

Coauthors: Shabbir Ahmed, George L. Nemhauser


The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases, such as the uncapacitated multi-echelon lot-sizing problem. We consider the computational complexity of MCCNFP as a function of the underlying network topology and the representation of the concave function by studying MCCNFP over a grid network with a general nonnegative separable concave function. We show that this problem is polynomial solvable when all source nodes are at the first echelon and all sink nodes are at the last echelon. The polynomiality argument relies on a combination of a particular dynamic programming formulation and a careful investigation of the extreme points of the underlying flow polyhedron. We derive an analytical formula for the inflow of any node under all extreme points, which generalizes Zangwill's result for the
multi-echelon lot-sizing problem.


Talk 1 of the invited session Tue.2.H 2032
"Trends in mixed integer programming III" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  Today, Ohio Payday Loans are legitimate, but there are illegal transactions that are still on the rise. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.