Polyhedra for Lot-Sizing with Wagner-Whitin Costs

Yves Pochet and Laurence A. Wolsey ()
Additional contact information
Yves Pochet: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium
Laurence A. Wolsey: CORE, Université catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium

No 1993010, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We examine the single-item lot-sizing problem with Wagner-Whitin costs over an n period horizon, i.e. Pt + ht ≥ Pt+l for t = 1, ... , n - 1, where Pt, ht are the unit production and storage costs in period t 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 start-up costs (ULSS) and the constant capacity problem (eLS), 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(n2 ) facets as opposed to O(2n) in the general case. For (eLS) and (BLS) no explicit polyhedral descriptions are known for the general case in the original space. Here we exhibit polyhedra with O(2n) facets having an O(n2 Iogn) separation algorithm for (eLS) and O(n3 ) for (BLS), as well as extended formulations with O(n2 ) constraints in both cases, O(n2 ) variables for (eLS) and O(n) variables for (BLS).

Date: 1993-03-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1993.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1993010

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().