Recognition: unknown
Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems
Pith reviewed 2026-05-10 17:21 UTC · model grok-4.3
The pith
Adaptive scoring lets Benders decomposition skip most subproblems while still reaching good solutions faster.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By training logistic regression models online on historical performance metrics and problem-specific features, then applying multi-criteria scores together with cut, proportion, or threshold stopping rules, Benders decomposition can solve only a subset of the recourse subproblems each iteration and still produce statistically significant gains in runtime and primal-dual integrals on survivable network design problems.
What carries the argument
The online logistic regression scoring model that predicts the probability a given subproblem will generate a useful Benders cut, combined with explicit stopping criteria that trade exploration against exploitation.
If this is right
- An oracle that knows in advance which subproblems will produce cuts reduces total solve time by 34.4 percent.
- Random selection of subproblems increases overall computation time compared with solving every subproblem.
- The best adaptive scoring rule produces statistically significant reductions in runtime and improvements in primal-dual integrals.
- More than half of the subproblems solved under full enumeration contribute no cuts and occur outside cut-free rounds.
Where Pith is reading between the lines
- The same online scoring idea could be applied to other iterative decomposition schemes in which subproblem value varies across iterations.
- Adding structural features derived from the underlying network might further improve the regression predictions without requiring more data.
- The explicit stopping criteria offer a tunable knob that could be combined with existing Benders acceleration techniques such as cut aggregation.
Load-bearing premise
That logistic regression models trained on the fly from past iterations can keep predicting which subproblems will yield cuts without overlooking ones that are essential for solution quality.
What would settle it
If the adaptive method is run on a fresh collection of instances and produces longer total runtimes or worse primal-dual gaps than full enumeration on the same instances, the claim of reliable improvement would be refuted.
Figures
read the original 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes adaptive subproblem selection strategies within Benders decomposition for a variant of the survivable network design problem. It develops multi-criteria scoring methods that combine historical performance metrics with instance features, trained online via logistic regression, and employs stopping rules based on cut limits, proportional solves, and score thresholds. On 135 test instances, the work reports that 52.1% of solved subproblems are unnecessary, an oracle with perfect foresight yields a 34.4% runtime reduction, random selection degrades performance relative to full enumeration, and the best proposed method delivers statistically significant gains in both runtime and primal-dual integrals.
Significance. If the empirical claims hold under closer scrutiny of controls and variance, the results supply concrete evidence that informed, adaptive selection of subproblems can accelerate Benders decomposition in scenario-rich problems without compromising solution quality. The quantification of unnecessary subproblems and the oracle benchmark are particularly useful for establishing the potential upside, while the online logistic regression approach illustrates a practical way to balance exploration and exploitation in decomposition algorithms.
major comments (2)
- [Computational experiments] Computational experiments section: the claim of statistically significant improvements in runtime and primal-dual integrals is load-bearing for the central empirical contribution, yet the manuscript provides no details on the statistical test(s) employed, exact p-values, effect sizes, or how variance and potential selection biases across the 135 instances were controlled, leaving the robustness of the significance assertions unverifiable.
- [Methodology for scoring and selection] Methodology for scoring and selection: the weakest assumption—that online logistic regression on historical metrics and features can reliably predict subproblem usefulness without missing important cuts—is not supported by any reported analysis of false-negative rates, cut-quality degradation, or cases where selected subsets produced inferior master-problem bounds relative to full enumeration.
minor comments (1)
- [Abstract] The abstract would benefit from explicitly naming the survivable network design variant and the precise set of instance features used in the logistic regression.
Simulated Author's Rebuttal
We thank the referee for the constructive feedback on our manuscript. The comments identify important gaps in the presentation of our empirical results and validation of the selection methodology. We address each point below and will revise the manuscript accordingly to strengthen the claims.
read point-by-point responses
-
Referee: [Computational experiments] Computational experiments section: the claim of statistically significant improvements in runtime and primal-dual integrals is load-bearing for the central empirical contribution, yet the manuscript provides no details on the statistical test(s) employed, exact p-values, effect sizes, or how variance and potential selection biases across the 135 instances were controlled, leaving the robustness of the significance assertions unverifiable.
Authors: We agree that the statistical details are missing and must be added for verifiability. In the revised manuscript we will expand the computational experiments section with: the exact test used (Wilcoxon signed-rank test on paired differences for runtime and primal-dual integral across the 135 instances), all reported p-values, effect sizes (rank-biserial correlation), and controls for variance (median and IQR reporting plus instance-level pairing to mitigate selection bias). These additions will be placed in a dedicated subsection on statistical analysis. revision: yes
-
Referee: [Methodology for scoring and selection] Methodology for scoring and selection: the weakest assumption—that online logistic regression on historical metrics and features can reliably predict subproblem usefulness without missing important cuts—is not supported by any reported analysis of false-negative rates, cut-quality degradation, or cases where selected subsets produced inferior master-problem bounds relative to full enumeration.
Authors: We acknowledge that the current manuscript does not contain an explicit analysis of false-negative rates or bound degradation. While the reported improvements in both runtime and primal-dual integrals relative to full enumeration provide indirect evidence that solution quality was not compromised, a direct examination is warranted. We will add to the revised paper: (i) false-negative rates of the logistic regression predictor computed via rolling cross-validation on the training history, and (ii) a comparison of final master-problem bounds (and primal-dual gaps) between the adaptive selection and full-enumeration runs on all 135 instances to quantify any degradation. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper describes an algorithmic framework for adaptive subproblem selection in Benders decomposition, using online logistic regression on historical metrics and instance features to score subproblems, combined with stopping rules. All central claims rest on empirical evaluation across 135 test instances, with explicit comparisons to full enumeration, random selection, and an oracle upper bound; runtime and primal-dual integral improvements are reported as statistically significant without any reduction of the method or results to self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The logistic regression serves as a standard predictive model whose outputs are validated externally against independent benchmarks rather than by construction, and no derivation chain or uniqueness theorem is invoked that collapses to the paper's own inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Benders cuts generated from subproblems are valid and tighten the master problem relaxation
Reference graph
Works this paper leans on
-
[1]
PhD thesis, Technische Universität Berlin, 2007
Tobias Achterberg.Constraint integer programming. PhD thesis, Technische Universität Berlin, 2007. doi:10.14279/depositonce-1634
-
[2]
Mathematical Programming Computation , volume =
Tobias Achterberg. SCIP: solving constraint integer programs.Mathematical Programming Compu- tation, 1(1):1–41, 2009.doi:10.1007/s12532-008-0001-1
-
[3]
Giovanni Andreello, Alberto Caprara, and Matteo Fischetti. Embedding cuts in a branch&cut framework: a computational study with{0, 1 2 }-cuts.INFORMS Journal on Computing, 19(2):229– 238, 2007.doi:10.1287/ijoc.1050.0162
-
[4]
Metric Inequalities and the Network Loading Problem
Pasquale Avella, Sara Mattia, and Antonio Sassano. Metric Inequalities and the Network Loading Problem. InDiscrete Optimization: The State of the Art, pages 53–84. Elsevier, 2004. doi: 10.1016/j.disopt.2006.10.002
-
[5]
Partitioning procedures for solving mixed-variables programming problems
Jacques F Benders. Partitioning procedures for solving mixed-variables programming problems. Numerische mathematik, 4(1):238–252, 1962.doi:10.1007/bf01386316
-
[6]
Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach to numerical computing.SIAM review, 59(1):65–98, 2017.doi:10.1137/141000671
-
[7]
Xavier Blanchot, François Clautiaux, Boris Detienne, Aurélien Froger, and Manuel Ruiz. The Benders by batch algorithm: Design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs.European Journal of Operational Research, 309(1):202–216, 2023.doi:10.1016/j.ejor.2023.01.004
-
[8]
S Borozan, S Giannelos, P Falugi, A Moreira, G Strbac, and T Zhang. Machine learning-enhanced Benders decomposition approach for the multi-stage stochastic transmission expansion planning problem.Electric Power Systems Research, 226:109956, 2024.doi:10.1016/j.epsr.2024.110985
-
[9]
Quentin Botton, Bernard Fortz, Luis Gouveia, and Michael Poss. Benders decomposition for the hop-constrained survivable network design problem.INFORMS Journal on Computing, 25(1):13–26, 2013.doi:10.1287/ijoc.1110.0472
-
[10]
Şifa Çelik, Layla Martin, Albert H Schrotenboer, and Tom Van Woensel. Exact two-step Benders decomposition for the time window assignment traveling salesperson problem.Transportation Science, 59(2):210–228, 2025.doi:10.1287/trsc.2024.0750. 11
-
[11]
An implicit optimization approach for survivable network design
Richard LY Chen, Amy Cohn, and Ali Pinar. An implicit optimization approach for survivable network design. In2011 IEEE Network Science Workshop, pages 159–163. IEEE, 2011. doi: 10.1016/j.ins.2011.09.004
-
[12]
Teodor Gabriel Crainic, Mike Hewitt, Francesca Maggioni, and Walter Rei. Partial Benders decomposition: general methodology and application to stochastic network design.Transportation Science, 55(2):414–435, 2021.doi:10.1287/trsc.2020.1022
-
[13]
Partial decomposition strategies for two- stage stochastic integer programs.CIRRELT (Université de Montréal), 88, 2014.doi:10.1007/ 978-3-662-04331-8_30
Teodor Gabriel Crainic, Mike Hewitt, and Walter Rei. Partial decomposition strategies for two- stage stochastic integer programs.CIRRELT (Université de Montréal), 88, 2014.doi:10.1007/ 978-3-662-04331-8_30
2014
-
[14]
Antoine Deza and Elias B Khalil. Machine learning for cutting planes in integer programming: A survey.arXiv preprint arXiv:2302.09166, 2023.doi:10.24963/ijcai.2023/739
-
[15]
Iain Dunning, Joey Huchette, and Miles Lubin. JuMP: A modeling language for mathematical optimization.SIAM Review, 59(2):295–320, 2017.doi:10.1137/15m1020575
-
[16]
Bernard Fortz and Michael Poss. An improved Benders decomposition applied to a multi-layer network design problem.Operations Research Letters, 37(5):359–364, 2009.doi:10.1016/j.orl. 2009.05.007
-
[17]
Gurobi Optimizer Reference Manual, 2024
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL:https://www.gurobi. com
2024
-
[18]
Mojtaba Hosseini and John Turner. Deepest Cuts for Benders Decomposition.Operations Research, 73(5):2591–2609, 2024.doi:10.1287/opre.2021.0503
-
[19]
F. Idzikowski, S. Orlowski, C. Raack, H. Woesner, and A. Wolisz. Dynamic routing at different layers in IP-over-WDM networks – Maximizing energy savings.Optical Switching and Networking, Special Issue on Green Communications, 2011.doi:10.1016/j.osn.2011.03.007
-
[20]
Koster, Manuel Kutschka, and Christian Raack
Arie M.C.A. Koster, Manuel Kutschka, and Christian Raack. Towards Robust Network Design using Integer Linear Programming Techniques. InProceedings of the NGI 2010, Paris, France, Paris, France, June 2010. Next Generation Internet.doi:10.1109/ngi.2010.5534462
-
[21]
Learning to Configure Separators in Branch-and-Cut
Sirui Li, Wenbin Ouyang, Max B Paulus, and Cathy Wu. Learning to Configure Separators in Branch-and-Cut. InAdvances in Neural Information Processing Systems, volume 37, 2023. doi:10.52202/075280-2622
-
[22]
Abdellah Bulaich Mehamdi, Mathieu Lacroix, and Sébastien Martin. Pricing filtering in Dantzig-Wolfe decomposition.Operations Research Letters, 58:107207, 2025.doi:10.1016/j.orl.2024.107207
-
[23]
The surprising performance of random partial Benders decomposition
Jean Pauphilet and Yupeng Wu. The surprising performance of random partial Benders decomposition. Optimization Online, 2025. 32181
2025
-
[24]
Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gendreau, and Walter Rei. The Benders decomposition algorithm: A literature review.European Journal of Operational Research, 259(3):801– 817, 2017.doi:10.1016/j.ejor.2016.12.005
-
[25]
Mathematical Programming , year =
Lara Scavuzzo, Karen Aardal, Andrea Lodi, and Neil Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming.Mathematical Programming, 2024.doi: 10.1007/s10107-024-02130-y
-
[26]
Reinforcement learning for integer programming: Learning to cut
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: Learning to cut. InInternational Conference on Machine Learning, pages 9367–9376. PMLR, 2020. doi:10.48550/arXiv.1906.04859
-
[27]
Cutting Plane Selection with Analytic Centers and Multiregression
Mark Turner, Timo Berthold, Mathieu Besançon, and Thorsten Koch. Cutting Plane Selection with Analytic Centers and Multiregression. InIntegration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), Lecture Notes in Computer Science, pages 52–68. Springer, 2023.doi:10.1007/978-3-031-33271-5_4. 12
-
[28]
Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming.Open Journal of Mathematical Optimization, 4:1–25, 2023. doi:10.5802/ojmo.25
-
[29]
Jie Wang, Zhihai Wang, Xijun Li, Yufei Kuang, Zhihao Shi, Fangzhou Zhu, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning to Cut via Hierarchical Sequence/Set Model for Efficient Mixed-Integer Programming.IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12):9697–9713, 2024.doi:10.1109/TPAMI.2024.3432716
-
[30]
B. P. Welford. Note on a method for calculating corrected sums of squares and products.Techno- metrics, 4(3):419–420, 1962.doi:10.1080/00401706.1962.10490022
-
[31]
Biometrics Bulletin , author =
Frank Wilcoxon. Individual comparisons by ranking methods.Biometrics Bulletin, 1(6):80–83, 1945. doi:10.2307/3001968
-
[32]
Wei Zhang, Kai Wang, Alexandre Jacquillat, and Shuaian Wang. Optimized scenario reduction: Solving large-scale stochastic programs with quality guarantees.INFORMS Journal on Computing, 35(4):886–908, 2023.doi:10.1287/ijoc.2023.1295
-
[33]
Xuefeng Zhang, Liangyu Chen, Zhengfeng Yang, and Zhenbing Zeng. Learning to select cutting planes in mixed-integer linear programming solving.Expert Systems with Applications, page 129924, 2025.doi:10.1016/j.eswa.2025.129924. 13 Appendix A Subproblem Statistics This section provides detailed subproblem statistics for all instances and the distribution of ...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.