Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching
Abstract
Many large-scale optimization problems decompose into a master problem and scenario subproblems.
Benders decomposition exploits this structure by iteratively solving the subproblems and adding constraints, called Benders cuts, to the master problem.
We study Benders cut filtering: given a set of Benders cuts produced in one iteration, which subset should be added to the master problem?
Adding all generated cuts can cause rapid master problem growth, whereas retaining fewer cuts may require more Benders iterations.
To our knowledge, few prior works have studied this question for Benders cuts.
Classical cut filtering techniques require modification because Benders cuts enforce constraints omitted from the master problem, whereas conventional cutting planes are optional inequalities that strengthen the relaxation.
We propose violation-based filtering, diversity-based filtering via k-medoids clustering on cosine distances, and a hybrid that selects a most-violated cut per cluster.
We compare these strategies with no filtering, random filtering, and our adaptation of SCIP's hybrid cut selector on an affine potential-based flow problem with topology switching and robustness scenarios.
On instances solved by all configurations, our hybrid approach reduces the shifted geometric mean solve time by about 45% compared to no filtering, and by 39% compared to our adaptation of SCIP's hybrid cut selector.
While violation-based filtering achieves a similar runtime, the hybrid approach requires about 17% fewer callback rounds.
These results demonstrate the effectiveness of Benders cut filtering on this problem class and motivate evaluation in other domains.