Deepest Cuts for Benders Decomposition
提出在Benders分解中通过选择消除最多无关解的最深割来减少迭代步数，实验表明该方法能显著缩短供应链分析问题的求解时间。
In the global economy, billions of dollars of merchandise are routed using software that, at its core, uses optimization technology. Over many decades, researchers have devised different approaches to make algorithms faster, and this is true for Benders decomposition as well. Benders speeds up finding an optimal solution to a problem with millions of variables and constraints by iteratively learning which constraints are important and considering only these constraints. Our idea is that selectively choosing the constraints that eliminate the largest number of irrelevant solutions at each step would lead to finding the optimal solution in the fewest number of Benders steps. Geometrically, this amounts to choosing so-called deep cuts. Of course, in attempting to minimize the number of steps, we do need to spend more time taking each individual step, but our experimental results on several types of problems arising in supply chain analytics show that this approach makes sense and significantly reduces the solution time.