Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching

Tim Donkiewicz, Oliver Gaul · 2026

Read Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching by Tim Donkiewicz, Oliver Gaul (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25764.txt.

Introduction

Donkiewicz and Gaul study how to filter Benders cuts in large optimization problems split into a master problem and scenario subproblems. Adding every cut makes the master problem grow fast, yet some cuts are never violated and need never be added. They test violation-based filtering, diversity-based filtering by clustering cuts, and a hybrid taking the most-violated cut per cluster. Each can add an aggregated cut preserving discarded information. On 149 flow instances, all informed strategies solved at least 125, against 91 unfiltered, and cut solve time by more than half.

Catalog record

CREATORTim Donkiewicz, Oliver Gaul
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47191
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.25764

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching Tim Donkiewicz, Oliver Gaul Abstract Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to be added to the master problem to guarantee optimality and feasibility of solutions, but we can avoid adding those constraints that are never violated. Adding fewer cuts per iteration can reduce the number of cuts added in total, but increase the number of iterations. In contrast, the cuts filtered for regular cut selection in mixed-integer programming solvers are optional and added exclusively to improve runtime behavior. We study Benders cut filtering : given the Benders cuts produced in an iteration, which subset should be added to the master problem? To our knowledge, few prior works have studied this question. We propose violation-based filtering (retaining the most-violated cuts), diversity-based filtering via k k -medoids clustering on pairwise cosine distances (adding an original cut closest to the cluster centroid), and a hybrid that selects a most-violated cut per cluster. Each strategy can be augmented with an aggregated cut that retains discarded information. Computational experiments on 149 instances of an affine potential-based flow problem with topology switching and robustness scenarios—solved via Benders decomposition—show that all informed filtering strategies solve at least 125 instances (vs. 91 for the unfiltered baseline), reducing shifted geometric mean solve time by 55–57%. The hybrid strategy attains the best geometric mean (271.89 s vs. 629.34 s, a 57% reduction, p < 0.001 p<0.001 ). Our work demonstrates the effectiveness of Benders cut filtering techniques on a particularly suitable problem class and motivates further study on the generalization to other domains. Keywords. Integer programming, Benders decomposition, cut filtering, potential-based flows, network optimization. 1 Introduction Many problems in discrete optimization decompose into a master problem and one or more subproblems. Benders decomposition [ 5 ] exploits this structure by iterating between the master and subproblems, where each subproblem solution generates a constraint—commonly called a Benders cut —that is added to the master problem. Branch-and-Benders-cut extends this by incorporating Benders cut generation into branch-and-bound: subproblems are solved in a callback at each feasible master candidate, and the resulting cuts are added as lazy constraints. When the number of subproblems is large, each iteration during branch-and-Benders-cut can produce many such constraints, and adding all of them leads to rapid master problem growth and can lead to longer re-optimization times as solving progresses. Still, this is the standard approach in the literature: all generated Benders cuts are added as hard constraints to the master problem and enforced explicitly in every subsequent iteration. We study a problem that we call Benders cut filtering : given the pool of Benders cuts generated in an iteration, which subset should be added as constraints to the master problem? This can be a relevant consideration: for our problem instances, even a random selection of 5% of cuts reduces solve times substantially, confirming that constraint growth in the master problem can be the primary bottleneck. Prior work has filtered Benders cuts with machine-learning classifiers trained offline on labeled examples [ 19 , 21 ] . However, to our knowledge, no prior work has studied filtering rules that do not require offline training on solved instances to determine which Benders cuts to add. Outside the Benders context, the analogous question, selecting which cutting planes to add from a pool, is well studied in MIP branch-and-cut solvers [ 1 , 3 , 35 ] . Solvers manage cut pools and apply quality criteria such as violation, pairwise distance, or objective parallelism to decide which cuts to enforce ( Section 2.5 ). In Benders decomposition, this pool-based management is not applicable directly: at least some Benders cuts have to be added as constraints, not as cuts optional to the formulation, to maintain correctness. We therefore adapt the principles of violation scoring and distance-based diversity to the Benders constraint setting. A separate line of work, Benders cut selection , addresses a different problem not considered in this paper: choosing a strongest cut among multiple dual solutions of a single subproblem ( Section 2.3 ). We propose three filtering strategies ( Section 4 ). Violation-based filtering retains the k most-violated cuts. Diversity-based filtering applies k -medoids clustering on pairwise cosine distances between cut coefficient vectors and selects one representative per cluster—an original cut nearest to the cluster centroid. Hybrid filtering clusters identically but selects a most-violated cut per cluster, combining violation with diversity. Random filtering is also considered as a baseline filtering technique. Each strategy can be augmented with an aggregated cut that retains at least some discarded information. The number of retained cuts is determined a priori or adaptively. We demonstrate our Benders cut filtering on affine potential-based flow problems [ 28 ] with topology switching and robustness scenarios. This setting is well-suited: subproblems are solvable as systems of linear equations [ 12 ] , producing many cuts cheaply, so that master constraint growth—rather than subproblem solving—is the bottleneck. Additionally, the subproblems are numerous and structurally similar, differing by at most two arcs in a graph with usually hundreds of arcs, which suggests that many cuts are similar. Computational experiments on 149 instances show that all filtering strategies significantly reduce solve times ( p<0.001 , Wilcoxon signed-rank test) compared to the unfiltered baseline (adding all cuts) common in the literature on Benders decomposition. Violation-based and diversity-based filtering solve 126 and 128 instances within the time limit (vs. 91 unfiltered), with 55–57% reductions in shifted geometric mean solve time. The hybrid strategy attains the best geometric mean (57% reduction) and solves 125 instances. Even random filtering solves 113, confirming that constraint growth is the bottleneck. 2 Related Work 2.1 Benders Decomposition and Cut Aggregation Benders [ 5 ] introduced a decomposition for mixed-integer programs that iterates between a master problem over complicating variables and a subproblem that generates constraints (Benders cuts) for the master. Rahmaniani et al. [ 29 ] provide a comprehensive survey. For two-stage stochastic programs, the L-shaped method of Van Slyke and Wets [ 36 ] introduces a single auxiliary variable \theta in the master that represents the expected recourse cost and, per iteration, adds one cut obtained by combining scenario duals with their probabilities to correct the master’s estimate of the expected recourse cost. Birge and Louveaux [ 7 ] introduce the multi-cut variant, which uses one auxiliary variable per scenario and adds one cut per scenario in each iteration; this can converge in far fewer iterations than the single-cut approach, at the cost of a larger master problem. Trukhanov et al. [ 34 ] dynamically adjust the aggregation level between single-cut and multi-cut by monitoring dual multipliers: scenario groups whose optimality cuts remain inactive (zero dual multiplier) for a threshold fraction of iterations are merged into a single aggregate. Their results demonstrate that an intermediate aggregation level can yield substantial computational savings. Notably, they also attempted to aggregate scenarios with similar cut gradients but found the

Read the complete text