We consider Benders decomposition for solving two-stage stochastic programs
with complete recourse based on finite samples of the uncertain parameters. We
define the Benders cuts binding at the final optimal solution or the ones
significantly improving bounds over iterations as valuable cuts. We propose a
learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut
classification step in each iteration to selectively generate cuts that are
more likely to be valuable cuts. The LearnBD algorithm includes two phases: (i)
sampling cuts and collecting information from training problems and (ii)
solving testing problems with a support vector machine (SVM) cut classifier. We
run the LearnBD algorithm on instances of capacitated facility location and
multi-commodity network design under uncertain demand. Our results show that
SVM cut classifier works effectively for identifying valuable cuts, and the
LearnBD algorithm reduces the total solving time of all instances for different
problems with various sizes and complexities.

本文提出了一种基于学习的 Benders 分解算法，使用支持向量机分类器识别关键切割面来加速解决双阶段随机规划问题，实验结果表明该方法可以显著降低不同大小和复杂度问题的求解时间。