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

Abstract

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. Incidentally, a special parametric transportation problem is also studied

Keywords:

• Concave Minimization
• Global Optimization
• Combinatorial Optimization
• Facility Location
• Production-Transportation Problem
• Rank r Property
• Parametric Transportation Problem
• Strongly Polynomial Algorithm

†On leave from Institute of Mathematics, P.O. Box 631, Hanoi, Vietnam

†On leave from Institute of Mathematics, P.O. Box 631, Hanoi, Vietnam

Notes

†On leave from Institute of Mathematics, P.O. Box 631, Hanoi, Vietnam