Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems

Tim Donkiewicz · 2026

Read Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems by Tim Donkiewicz (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-09031.txt.

Introduction

Donkiewicz studies how to pick subproblems as needed in Benders decomposition for tough network design. Benders splits first-stage master choices from second-stage recourse actions, tuning the master problem with cuts over rounds. Solving every task each round is the norm, but with many cases, solving only a chosen subset can save compute. The paper gauges the gain from solving only cut-yielding tasks. Its best scoring and picking method lifts runtime and primal-dual integrals a lot, while random picks perform far worse than full listing.

Catalog record

CREATORTim Donkiewicz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63224
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

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

Browse the full library · About the Tower of Babel

Full text

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

Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems Tim Donkiewicz Abstract Scenario-based optimization problems can be solved via Benders decomposition, which separates first-stage (master problem) decisions from second-stage (subproblem) recourse actions and iteratively refines the master problem with Benders cuts. In conventional Benders decomposition, all subproblems are solved at each iteration. For problems with many scenarios, solving only a selected subset can reduce computation. We quantify the potential in selecting only those subproblems that yield cuts, and develop subproblem scoring and selection strategies. The proposed multi-criteria scoring methods combine historical subproblem performance metrics with problem-specific features, trained online via logistic regression to adapt to the changing likelihood of subproblem usefulness. Multiple stopping criteria balance exploration and exploitation: cut limits, proportional solve limits, and score thresholds. We evaluate our approach on a variant of the survivable network design problem, which serves as a testbed due to its natural decomposition into many subproblems of varying importance. Computational experiments on 135 test instances demonstrate the potential and practical performance of subproblem selection. Analysis reveals that 52.1% of all subproblems solved are unnecessary (they contribute no cuts and occur outside cut-free rounds). An oracle with perfect foresight reduces total solve times by 34.4%. Random selection performs significantly worse than full enumeration, showing that naive strategies can degrade performance. Our best-scoring and selection method achieves statistically significant improvements in both runtime and primal-dual integrals. These results provide empirical evidence that informed subproblem selection can improve Benders decomposition in this setting, while highlighting challenges in developing reliable prediction models. Whether these findings extend to other problem classes remains an open question for future work. Keywords: Integer programming, Benders decomposition, subproblem selection, survivable network design, machine learning, operations research 1 Introduction Benders decomposition [ 5 ] is a powerful technique for structured optimization problems, separating first-stage decisions from second-stage recourse problems. In an iterative manner, the master problem is solved to propose first-stage solutions. Then, subproblems corresponding to different scenarios are solved to check feasibility or optimality of the proposed solution. If any subproblem is infeasible or more expensive than expected by the master problem’s estimation, Benders cuts are generated and added to the master problem to refine the solution space. This process repeats until the branch-and-bound algorithm terminates. Modern implementations of Benders decomposition apply Branch-and-Benders-cut [ 24 ] , integrating Benders cuts as lazy constraints within a branch-and-bound framework for mixed-integer programming (see Figure 1 ). Solve Master Problem (Local LP Relaxation) Solve All Subproblems (One per Scenario) Cuts found? Add Benders Cuts yes branching decisions no Figure 1: Basic Branch-and-Benders-cut framework. However, when the number of scenarios grows large, solving all subproblems at each iteration becomes computationally prohibitive. Through computational experiments on survivable network design (SND) instances, we observe that 52.1% of subproblems solved under conventional Benders decomposition are unnecessary. This empirical observation motivates a data-driven computational approach to adaptive subproblem selection—we aim to dynamically learn which subproblems are most likely to contribute to the solving process by generating Benders cuts. To that end, we observe patterns in cut generation behavior, then prioritize subproblems accordingly, and stop once enough subproblems were solved (and at least one cut was generated). We use SND as a testbed for developing adaptive subproblem selection strategies. SND problems exhibit characteristics that make them particularly suitable for this study: they naturally decompose into many subproblems (one per failure scenario), these subproblems vary substantially in their importance, and some scenarios can dominate others due to network topology. While our goal is not to advance the state-of-the-art for SND solving specifically, this problem class provides a suitable environment to demonstrate subproblem selection techniques. To our knowledge, adaptive subproblem selection based on computational pattern learning has not been successfully demonstrated for Benders decomposition in prior work. We provide a first empirical study addressing this gap, using SND as our testbed. Our four main contributions are grounded in empirical analysis: First, we develop an oracle baseline that quantifies the computational potential of perfect subproblem selection through empirical measurements. Second, we develop a multi-criteria scoring mechanism that combines observed historical performance metrics (cut generation frequency, cumulative contribution, recency) with computational features extracted from the current solution (failed edge capacity, flow, utilization, centrality). Third, we introduce an online learning approach using logistic regression that learns from computational observations during solving. We train incrementally on each subproblem outcome to predict scenario infeasibility and adapt to evolving cut generation patterns without requiring problem-specific tuning or offline training. The online training incurs a reasonable computational overhead—one update is comparable to solving a single subproblem—making it practical for real-time deployment. Fourth, we implement partial subproblem solving with multiple stopping criteria that balance computational effort between exploration and exploitation based on empirical performance indicators. Our goal is twofold: demonstrate through computational experiments on SND instances that dynamically learning from empirical observations can achieve statistically significant improvements over the baseline, and quantify via the oracle how much additional computational improvement could be attained with more sophisticated pattern recognition. Validating these findings on other problem classes remains a direction for future research. 2 Related Work Benders [ 5 ] first introduced the Benders decomposition algorithm for mixed-integer programming. Rahmaniani et al. [ 24 ] provide a comprehensive modern survey and an overview of Branch-and-Benders-cut. Benders decomposition has been applied to survivable network design problems [ 9 , 16 ] . The SNDlib benchmark instances [ 19 , 20 ] are widely used for evaluating network design algorithms. 2.1 Scenario Retention, Selection, and Partitioning An approach to managing computational burden is to retain selected second-stage variables explicitly in the master problem rather than projecting them out through Benders cuts. Crainic et al. [ 13 , 12 ] develop partial decomposition strategies for two-stage integer programs and stochastic multicommodity network design. Pauphilet et al. [ 23 ] show that random variable retention can achieve good performance. These methods fundamentally change the master problem structure. Rather than modifying the master problem structure, scenario selection methods choose which subproblems to solve at each iteration. Rahmaniani et al. [ 24 ] note that solving only a subset of subproblems—especially early in the algorithm—can reduce computational burden, though such strategies remain underexplored for combinatorial optimization. Chen et al. [ 11 ] reformulate the feasibility check for single-commodity survivable network design using an oracle based on minimum cut computations to identify violated scenarios to examine. Zhang et al. [ 32 ] propose optimization-based scenario reduction to approximate the recourse function while maintaining tight optimality gaps. Blanchot et al. [ 7 ] stop solving subproblems after the sum of the violation of obtained optimality cuts exceeds the current gap, often solving only 1% of subproblems. Mehamdi and Gendron [ 22 ] select pricing subproblems to solve in partial pricing in Branch-and-Price based on dual information. Celik and Toriello [ 10 ] develop a scenario-retention strategy that avoids resolving subproblems remaining feasible across iterations. Learning-based approaches have also emerged: Borozan et al. [ 8 ] use machine learning to predict which scenarios generate cuts binding in the final solution. These approaches adaptively select which subproblems to examine without modifying the problem structure. 2.2 Scoring Mechanisms for Algorithmic Decisions The use of scoring functions to prioritize algorithmic decisions is common in

Read the complete text