Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation
- 1 December 2002
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 48 (12), 1587-1602
- https://doi.org/10.1287/mnsc.48.12.1587.442
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.Other Versions
This publication has 42 references indexed in Scilit:
- bc-opt: a branch-and-cut code for mixed integer programsMathematical Programming, 1999
- Lotsizing with backlogging and start-ups: the case of Wagner–Whitin costsOperations Research Letters, 1999
- On the discrete lot-sizing and scheduling problem with Wagner-Whitin costsOperations Research Letters, 1997
- A linear description of the discrete lot-sizing and scheduling problemEuropean Journal of Operational Research, 1994
- Batching decisions: structure and modelsEuropean Journal of Operational Research, 1994
- The single-item discrete lotsizing and scheduling problem: optimization by linear and dynamic programmingDiscrete Applied Mathematics, 1994
- Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problemsEuropean Journal of Operational Research, 1993
- The discrete lot-sizing and scheduling problemEuropean Journal of Operational Research, 1990
- Valid inequalities and separation for capacitated economic lot sizingOperations Research Letters, 1988
- Uncapacitated lot-sizing: The convex hull of solutionsPublished by Springer Science and Business Media LLC ,1984