ISSN:
1436-4646
Keywords:
Lot-sizing models
;
Polyhedral combinatorics
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We examine the single-item lot-sizing problem with Wagner—Whitin costs over ann period horizon, i.e.p t+ht⩾pt+1 fort = 1, ⋯,n−1, wherep t, ht are the unit production and storage costs in periodt respectively, so it always pays to produce as late as possible. We describe integral polyhedra whose solution as linear programs solve the uncapacitated problem (ULS), the uncapacitated problem with backlogging (BLS), the uncapacitated problem with startup costs (ULSS) and the constant capacity problem (CLS), respectively. The polyhedra, extended formulations and separation algorithms are much simpler than in the general cost case. In particular for models ULS and ULSS the polyhedra in the original space have only O(n 2) facets as opposed to O(2 n ) in the general case. For CLS and BLS no explicit polyhedral descriptions are known for the general case in the original space. Here we exhibit polyhedra with O(2 n ) facets having an O(n 2 logn) separation algorithm for CLS and O(n 3) for BLS, as well as extended formulations with O(n 2) constraints in both cases, O(n 2) variables for CLS and O(n) variables for BLS.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582225
Permalink
