Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation

Laurence A. Wolsey ()
Additional contact information
Laurence A. Wolsey: CORE and INMA, Université Catholique de Louvain, Belgium

Management Science, 2002, vol. 48, issue 12, 1587-1602

Abstract: Based on research on the polyhedral structure of lot-sizing models over the last 20 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). Three distinct multi-item lot-sizing instances are then presented to demonstrate the approach, and comparative computational results are presented. Finally, we also use the classification to point out what appear to be some of the important open questions and challenges.

Keywords: Lot Sizing; Production Planning; Classification; Convex Hull; Extended Formulation; Mixed-Integer Programming (search for similar items in EconPapers)
Date: 2002
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (33)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.48.12.1587.442 (application/pdf)

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:inm:ormnsc:v:48:y:2002:i:12:p:1587-1602

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().