Relaxations for two-level multi-item lot-sizing problems

• 成果类型: Article
• 署名作者: Van Vyve, Mathieu; Wolsey, Laurence A.; Yaman, Hande
• 署名单位: Ihsan Dogramaci Bilkent University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0702-8
• 发表日期: 2014
• 页码: 495-523
• 关键词: COMPUTATIONAL-COMPLEXITY; convex-hull; models; algorithms

摘要

We consider several variants of the two-level lot-sizing problem with one item at the upper level facing dependent demand, and multiple items or clients at the lower level, facing independent demands. We first show that under a natural cost assumption, it is sufficient to optimize over a stock-dominant relaxation. We further study the polyhedral structure of a strong relaxation of this problem involving only initial inventory variables and setup variables. We consider several variants: uncapacitated at both levels with or without start-up costs, uncapacitated at the upper level and constant capacity at the lower level, constant capacity at both levels. We finally demonstrate how the strong formulations described improve our ability to solve instances with up to several dozens of periods and a few hundred products.