Literature review on Benders cut selection and a multiple cut generation scheme

One way to improve the efficiency of the Benders Decomposition Method is the generation of high-quality cuts. This paper presents a literature review on Benders cut selection methods, followed by the development of a multiple cut generation scheme that remains effective regardless of whether the Subproblem is decomposable or not. The proposed approach builds upon the work of Brandenberg and Stursberg (Mathematical Methods of Operations Research, 94:383–412, 2021), who developed a unifying framework for generating Benders cuts by identifying appropriate parametrizations for the cost vector of the objective function used to optimize over the alternative polyhedron. Our analytical results provide further insights into the structure of those parametrizations. Experiments are conducted to demonstrate the effectiveness of our method compared to the classical Benders Algorithm.

提升本德分解法（Benders Decomposition Method）效率的关键途径之一是生成高质量的本德割（Benders cut）。本文首先针对本德割选择方法展开了系统性文献综述，随后提出了一种多割生成方案，该方案无论子问题（Subproblem）是否可分解，均能保持有效。所提方法基于Brandenberg与Stursberg于2021年发表在《运筹学的数学方法》（Mathematical Methods of Operations Research）第94卷第383–412页的研究成果——他们通过为用于优化备选多面体（alternative polyhedron）的目标函数代价向量确定合适的参数化方式，构建了一套生成本德割的统一框架。本文的分析结果进一步深化了对这类参数化方式结构的认知，同时通过与经典本德算法（Benders Algorithm）的对照实验，验证了所提方法的实际有效性。