Scenario-dominance to multi-stage stochastic lot-sizing and knapsack problems
本文提出强场景支配割，用于加速求解多阶段随机混合整数规划中的两类经典问题：随机有容量多物品批量问题和随机动态多维背包问题，实验表明该方法能显著缩短求解时间且解质量接近最优。
This paper presents strong scenario dominance cuts for effectively solving the multi-stage stochastic mixed-integer programs (M-SMIPs), specifically focusing on the two most well-known M-SMIPs: stochastic capacitated multi-item lot-sizing (S-MCLSP) and the stochastic dynamic multi-dimensional knapsack (S-MKP) problems. Scenario dominance is characterized by a partial ordering of scenarios based on the pairwise comparisons of random variable realizations in a scenario tree of a stochastic program. In this paper, we study the implications of scenario-dominance relations and inferences obtained by solving scenario sub-problems to drive new strong cutting planes to solve S-MCLSP and S-MKP instances faster. Computational experiments demonstrate that our strong scenario dominance cuts can significantly reduce the solution time for such M-SMIP problems with an average of 0.06% deviation from the optimal solution. The results with up to 81 random variables for S-MKP show that strong dominance cuts improve the state-of-the-art solver solution of two hours by 0.13% in five minutes. The proposed framework can also be applied to other scenario-based optimization problems.