Lotsizing with backlogging and start-ups: The case of Wagner–Whitin costs

We examine the uncapacitated single-item lotsizing problem with backlogging and start-up costs where Wagner–Whitin costs are assumed. We generalize some theoretical results for the polyhedral description of the convex hull of feasible solutions for models that can be viewed as particular cases of the one treated in this paper (models without start-up costs and models where backlog is not allowed). In the presence of Wagner–Whitin costs (which satisfy pt + &htilde;t⁺ − pt+1 ⩾ 0, for 0 ⩽ t ⩽ n − 1, and pt+1 + &htilde;t⁻ − pt ⩾ 0, for 1 ⩽ t ⩽ n, where pt, &htilde;t⁺ and &htilde;t⁻ are the unit production, storage and backlogging costs; in the case that unit production costs are constant over time, the Wagner–Whitin assumption corresponds to non-negative holding costs and backlogging costs) we present a linear extended formulation with O(n) variables and O(n²) constraints. By projection, we obtain a linear formulation in the original space of variables with an exponential number of constraints.