New valid inequalities and formulations for the static joint Chance-constrained Lot-sizing problem

• 成果类型: Article
• 署名作者: Zhang, Zeyang; Gao, Chuanhou; Luedtke, James
• 署名单位: Zhejiang University; University of Wisconsin System; University of Wisconsin Madison
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01847-y
• 发表日期: 2023
• 页码: 639-669
• 关键词: equivalents

摘要

We study the static joint chance-constrained lot-sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the inventory variables are then determined by the demand realizations. The joint chance constraint imposes a service level requirement that the probability that all demands are met on time be above a threshold. We model uncertain outcomes with a finite set of scenarios and begin by applying existing results about chance-constrained programming to obtain an initial extended mixed-integer programming formulation. We further strengthen this formulation with a new class of valid inequalities that generalizes the classical (l, S) inequalities for the deterministic uncapacitated lotsizing problem. In addition, we prove an optimality condition of the solutions under a modified Wagner-Whitin condition, and based on this derive a new extended mixed-integer programming formulation. This formulation is further extended to the case with constant capacities. We conduct a thorough computational study demonstrating the effectiveness of the new valid inequalities and extended formulation.