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

Wednesday, September 25, 2002 - 1:30pm - 2:20pm
Keller 3-180
Laurence Wolsey (Université Catholique de Louvain)
Based on research on the polyhedral structure of lot-sizing models over the last twenty years, 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 approach is based on 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.

Slides for Classification and Reformulation: a Direct Way to Tackle Multi-Item Lot-Sizing Problems: