We examine the uncapacitated single-item lotsizing problem with backlogging
and start-up costs where Wagner-Whitin costs are assumed. We generalize so
me theoretical results obtained in [5] for the polyhedral description of th
e convex hull of feasible solutions for models that can be viewed as partic
ular 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 p(t) + (h) over tilde(t)(+) - p(t+1) greater than or e
qual to 0, for 0 less than or equal to t less than or equal to n - 1, and p
(t+1) + (h) over tilde(t)(-) - p(t) greater than or equal to 0, for 1 less
than or equal to t less than or equal to n, where p(t), (h) over tilde(t)() and (h) over tilde(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 back
logging costs) we present a linear extended formulation with O(n) variables
and O(n(2)) constraints. By projection, we obtain a linear formulation in
the original space of variables with an exponential number of constraints.
(C) 1999 Elsevier Science B.V. All rights reserved.