Progressive hedging for multi-stage stochastic lot sizing problems with setup carry-over under uncertain demand
研究了多阶段需求不确定下多产品多层级有产能的批量问题，提出渐进对冲算法，通过调整惩罚参数和元启发式策略提高收敛速度，在基准实例上达到接近最优解且运行时间更短。
We investigate multi-stage demand uncertainty for the multi-item multi-echelon capacitated lot sizing problem with setup carry-over. Considering a multi-stage decision framework helps to quantify the benefits of being able to adapt decisions to newly available information. The drawback is that multi-stage stochastic optimization approaches lead to very challenging formulations. This is because they usually rely on scenario tree representations of the uncertainty, which grow exponentially in the number of decision stages. Thus, even for a moderate number of decision stages it becomes difficult to solve the problem by means of a compact optimization model. To address this issue, we propose a progressive hedging algorithm and we investigate and tune the crucial penalty parameter that influences the conflicting goals of fast convergence and solution quality. While low penalty parameters usually lead to high quality solutions, this comes at the cost of slow convergence. To tackle this problem, we adapt metaheuristic adjustment strategies to guide the algorithm towards a consensus more efficiently. Furthermore, we consider several options to compute the consensus solution. While averaging the subproblem decisions is a common choice, we also apply a majority voting procedure. We test different algorithm configurations and compare the results of progressive hedging to the solutions obtained by solving a compact optimization model on well-known benchmark instances. For several problem instances the progressive hedging algorithm converges to solutions within 1% of the cost of the compact model’s solution, while requiring shorter runtimes. • Define a multi-stage stochastic lot sizing problem with setup carry-over. • Analyze the penalty parameter’s role in the progressive hedging method’s performance. • Apply metaheuristic strategies to enhance the algorithm’s convergence behavior. • Find varying algorithmic behavior for different consensus calculation procedures. • Runtime of tuned progressive hedging outperforms compact model within 1% cost range.