A multi-item production planning model with setup times: algorithms, reformulations, and polyhedral characterizations for a special case

Andrew J. Miller, George L. Nemhauser and Martin W.P. Savelsbergh

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

Abstract: We study a special case of a structured mixed integer programming model that arises in a number of applications. For the most general case of the model, called PI, we have earlier analyzed the polyhedral structure (Miller et al. [2000a]), including identifying facet-defining valid inequalities. PI is N P-hard; in this paper we focus on a special case, called PIC, that is polynomially solvable. We describe a polynomial algorithm for PIC, and we then use this algorithm to derive an extended formulation of polynomial size for PIC. Projecting from this extended formulation onto the original space of variables, we show that the set of inequalities presented for PI in Miller et al. [2000a] is sufficient to enable us to solve the special case PIC by linear programming. Finally, for PIC, we describe fast combinatorial separation algorithms for these inequalities.

Keywords: Mixed integer programming; polyhedral combinatorics; production planning; capacitated lot-sizing; fixed charge network flow; setup times (search for similar items in EconPapers)
Date: 2001-01
References: Add references at CitEc
Citations:

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

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