Strongly polynomial algorithm for a production-transportation problem with concave production cost

This paper presents a strongly polynomial algorithm for a special concave minimization problem which is a production-transportation problem involving concave production cost and linear transportation cost. The method used is characterized by a systematic exploitation of the specific structure of the problem: monotonicity property of the objective function, sparse nonconvexity (possibility of locating the nonconvexity in a low dimensional space) and combinatorial properties inherited from the network structure. Incidentially, a special parametric transportation problem is also studied.