A polynomial time algorithm for convex cost lot-sizing problems Academic Article uri icon


  • 2015 Elsevier B.V. Abstract This paper provides a polynomial-time algorithm for economic lot-sizing problems with convex costs in the production and inventory quantities. The resulting algorithm is based on a primal-dual approach that takes advantage of the problem's special structure. This approach improves upon existing results in the literature, which are either pseudo-polynomial or focus on special cases. We apply the approach to a production planning problem with price-dependent supply, leading to an improved bound on the algorithm's running time for a special case.

published proceedings


author list (cited authors)

  • Teksan, Z. M., & Geunes, J.

citation count

  • 5

complete list of authors

  • Teksan, Z Melis||Geunes, Joseph

publication date

  • July 2015