Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

0.00 Avg rating0 Votes
Article ID: iaor200971048
Country: Germany
Volume: 6
Issue: 4
Start Page Number: 447
End Page Number: 457
Publication Date: Oct 2009
Journal: Computational Management Science
Authors: , ,
Keywords: programming: dynamic, programming: integer
Abstract:

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n 4 m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.

Reviews

Required fields are marked *. Your email address will not be published.