We study the lot-sizing problem with piecewise concave production costs and concave holding costs. This problem is a generalization of the lot-sizing problem with quantity discounts, minimum order quantities, capacities, overloading, subcontracting or a combination of these. We develop a dynamic programming (DP) algorithm to solve this problem and answer an open question in the literature: we show that the problem is polynomially solvable when the breakpoints of the production cost function are time invariant and the number of breakpoints is fixed. For the special cases with capacities and subcontracting, the time complexity of our DP algorithm is as good as the complexity of algorithms available in the literature. We report the results of a computational experiment where the DP is able to solve instances that are hard for a mixed-integer programming (MIP) solver. We enhance the MIP formulation with valid inequalities based on mixing sets and use a cut-and-branch algorithm to compute better bounds. We propose a state space reduction based heuristic algorithm for large instances and show that the solutions are of good quality by comparing them with the bounds obtained from the cut-and-branch.
Citation
Technical Report, Department of Industrial Engineering, Bilkent University, Bilkent 06800, Ankara, Turkey, February 2013.