Single item lot-sizing with non-decreasing capacities

We consider the single item lot-sizing problem with capacities that are non-decreasing overtime. When the cost function is i) non-speculative or Wagner-Whitin (for instance, constantunit production costs and non-negative unit holding costs), and ii) the production set-upcosts are non-increasing over time, it is known that the minimum cost lot-sizing problem ispolynomially solvable using dynamic programming.When the capacities are non-decreasing, we derive a compact mixed integer programmingreformulation whose linear programming relaxation solves the lot-sizing problem tooptimality when the objective function satisfies i) and ii). The formulation is based onmixing set relaxations and reduces to the (known) convex hull of solutions when thecapacities are constant over time.We illustrate the use and effectiveness of this improved LP formulation on a new testinstances, including instances with and without Wagner-Whitin costs, and with both nondecreasingand arbitrary capacities over time....