On the Wagner-Whitin lot-sizing polyhedron

Olivier Pereira and Laurence Wolsey

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

Abstract: We study a family of unbounded polyhedra arising in the study of uncapacitated lot-sizing problems with Wagner-Whitin costs. With n the number of periods, we completely characterize the bounded faces of maximal dimension, and derive an O(n2) algorithm to express any point within the polyhedron asa convex combination of extreme points and extreme rays. We also study adjacency on the polyhedra, and give a simple O(n) test for adjacency. Finally we observe that if we optimize over these polyhedra, the face of optimal solutions can be found in O(n2).

Date: 2000-03
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2000.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:2000023

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 ().