Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut

Andrew Miller, George Nemhauser and Martin Savelsbergh

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

Abstract: Instances of the multi-item capacitated lot-sizing problem with setup times (MCL) often appear in practice, either in standard form or with additional constraints, but they have generally been difficult to solve to optimality. In MCL demand for multiple items must be met over a time horizon, items compete for a shared capacity, and each setup uses up some of this capacity. In this paper we use results concerning the polyhedral structure of simplified models obtained from a single time period of MCL to obtain strong valid inequalities for MCL. To the best of our knowledge, these inequalities are the first to consider demand for multiple items and the joint capacity restriction simultaneously. We also discuss how to implement these inequalities successfully in a branch-and-cut algorithm. Our computational results suggest that our contributions represent significant progress in solving instances of MCL.

Keywords: Mixed integer programming; cutting planes; production planning; capacitated lot-sizing; setup times. (search for similar items in EconPapers)
Date: 2000-08
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

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:2000039

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