Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation
提出一种分类方法，将多物品批量问题分解为单物品子问题，利用已知的紧扩展公式和有效不等式，使非专业人士可通过商业求解器高效求解，并用实例验证了效果。
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.