期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2002
卷号：2002
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：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 prob-
lems 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 com-
mercial 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.
