Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation

Laurence Wolsey

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

Abstract: Based on research on the polyhedral structure of lot-sizing models over the last twenty years, we claim that there is a nontrivial fraction of practical lot-sizing problems that can now be solved by nonspecialists just by taking an appropriate a priori reformulation of the problem, and then feeding the resulting formulation into a commercial mixed integer programming solver. This claim uses the fact that many multi-item problems decompose naturally into a set of single-item problems with linking constraints, and that there is now a large body of knowledge about single-item problems. To put this knowledge to use, we propose a classification of lot-sizing problems (in large part single-item), and then indicate in a set of Tables what is known about a particular problem class, and how useful it might be. Specifically we indicate for each class i) whether a tight extended formulation is known, and its size, ii) whether one or more families of valid inequalities are known defining the convex hull of solutions, and the complexity of the corresponding separation algorithms, and iii) the complexity of the corresponding optimization algorithms (which would be useful if a column generation or Lagrangian relaxation approach was envisaged).

Keywords: Lot-sizing; Production Planning; Classification; Convex Hull; Extended Formulation; Mixed Integer Programming (search for similar items in EconPapers)
Date: 2002-03
References: Add references at CitEc
Citations: View citations in EconPapers (32)

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

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