pith. sign in

arxiv: 2602.11490 · v2 · submitted 2026-02-12 · 🧮 math.OC

An Efficient Hybrid Heuristic for the Transmission Expansion Planning under Uncertainty

Yure Rocha , Teobaldo Bulh\~oes , Anand Subramanian , Joaquim Dias Garcia This is my paper

Pith reviewed 2026-05-16 06:15 UTC · model grok-4.3

classification 🧮 math.OC
keywords stochastic transmission expansion planningprogressive hedginghybrid heuristicdestroy-and-repairbeam searchrenewable uncertaintypower system optimization
0
0 comments X

The pith

A progressive hedging hybrid heuristic improves solution quality by 5.28 percent on average for large stochastic transmission expansion problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an algorithm for stochastic transmission expansion planning that minimizes total investment and operating costs while handling uncertainty in renewable generation and electricity demand. It decomposes the problem across scenarios using progressive hedging and then solves the resulting subproblems with a destroy-and-repair operator, beam search, and a mixed-integer programming solver. On six large test systems adapted from the California test system, the method produces lower-cost plans than a strong baseline that uses the same subproblem solver without the decomposition step. A reader would care because these improvements translate directly into cheaper and more reliable transmission infrastructure decisions for grids with growing shares of variable renewables.

Core claim

The authors show that wrapping an integrated destroy-and-repair and beam-search procedure inside progressive hedging yields transmission expansion plans whose total cost is 5.28 percent lower on average than those obtained by the same integrated procedure used without scenario decomposition, across six systems of up to 10,000 nodes and within a two-hour time limit.

What carries the argument

Progressive hedging decomposition of the stochastic problem, with each scenario subproblem solved by a destroy-and-repair operator followed by beam search and mixed-integer programming.

If this is right

  • The approach produces lower total transmission investment plus generation costs under uncertainty in renewables and demand.
  • It scales to systems with up to 10,000 nodes and multiple stochastic scenarios derived from California test system parameters.
  • The hybrid framework can be reused for other large-scale stochastic power-system planning problems that admit scenario decomposition.
  • Within the same computational budget it returns measurably better plans than applying the integrated subproblem solver directly to the full model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same decomposition-plus-hybrid-subproblem pattern could be tested on stochastic planning problems outside power systems, such as water-network or transport-network expansion.
  • Parallel execution of the independent scenario subproblems would likely reduce wall-clock time further without changing solution quality.
  • Replacing the current scenario set with one that includes correlated extreme-weather events could show whether the method remains robust when uncertainty is more structured.

Load-bearing premise

The destroy-and-repair operator combined with beam search reliably produces high-quality solutions to the subproblems generated by progressive hedging on the adapted instances.

What would settle it

On the California test system or the other five instances, if the proposed method fails to deliver at least a 4 percent cost reduction relative to the non-decomposition baseline inside two hours, the claimed performance advantage would be refuted.

Figures

Figures reproduced from arXiv: 2602.11490 by Anand Subramanian, Joaquim Dias Garcia, Teobaldo Bulh\~oes, Yure Rocha.

Figure 1
Figure 1. Figure 1: Partial BS execution for an instance with 5 buses, 6 existing lines and 12 candidate circuits. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
read the original abstract

We address the stochastic transmission expansion planning (STEP) problem under uncertainty in renewable generation capacity and demand. STEP's objective is to minimize total transmission investment and generation costs. To tackle the computational challenges posed by large-scale systems, we propose a heuristic strategy that combines the progressive hedging (PH) algorithm for scenario-wise decomposition with an integrated approach for solving the resulting subproblems. The latter combines a destroy-and-repair operator, a beam search procedure, and a mixed-integer programming solver. The proposed framework is evaluated on large-scale systems from the literature with up to 10000 nodes, adapted to stochastic scenarios using parameters from the California test system (CATS). Compared with a non-trivial baseline algorithm that includes the same integrated approach, the proposed PH-based method consistently improved solution quality for the six systems considered (including CATS), achieving an average cost improvement of 5.28% within a 2-hour time limit.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a hybrid heuristic for stochastic transmission expansion planning (STEP) under uncertainty in renewable generation capacity and demand. It decomposes the problem via progressive hedging (PH) and solves the resulting scenario subproblems with an integrated destroy-and-repair operator, beam search, and MIP solver. On six literature-derived systems (up to 10,000 nodes) adapted using CATS parameters, the PH-based method reports a 5.28% average cost improvement over a non-trivial baseline that uses the identical subproblem solver, all within a 2-hour time limit.

Significance. If the subproblem solutions are reliably high-quality, the approach offers a practical algorithmic route to large-scale STEP instances that are otherwise intractable, with demonstrated gains on standard test systems including CATS. The use of literature benchmarks and a non-trivial baseline strengthens the empirical case for hybrid decomposition heuristics in power-system optimization.

major comments (2)
  1. [§5 (computational results on adapted CATS instances)] The central claim of a 5.28% average improvement (abstract and results) rests on the assumption that the destroy-and-repair operator plus beam search returns high-quality feasible solutions to the PH-generated subproblems. On the largest adapted instances (up to 10,000 nodes), any systematic shortfall in subproblem quality would imply that both the proposed method and the baseline optimize over the same weak approximations, rendering the reported gap potentially attributable to tuning rather than PH decomposition itself.
  2. [§4 (subproblem solution procedure) and §5] No metrics are reported on subproblem optimality gaps, solution quality relative to exact MIP solves on smaller instances, or sensitivity to beam-search width and destroy-and-repair parameters. These omissions are load-bearing because the baseline already incorporates the identical integrated solver, so the incremental benefit of PH cannot be isolated without evidence that the subproblems are solved to comparable accuracy in both approaches.
minor comments (2)
  1. [Abstract] The abstract omits any description of scenario generation for renewable capacity and demand uncertainty; this should be added with explicit parameter values drawn from CATS to support reproducibility.
  2. [§5 (tables and figures)] Table captions and axis labels in the computational results should explicitly state whether reported costs are expected values or scenario-wise, and whether the 2-hour limit includes all PH iterations.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback and for recognizing the practical relevance of our hybrid progressive hedging heuristic for large-scale stochastic transmission expansion planning. We address the two major comments below by clarifying the role of subproblem quality and committing to additional metrics that isolate the contribution of the PH decomposition.

read point-by-point responses

  1. Referee: [§5 (computational results on adapted CATS instances)] The central claim of a 5.28% average improvement (abstract and results) rests on the assumption that the destroy-and-repair operator plus beam search returns high-quality feasible solutions to the PH-generated subproblems. On the largest adapted instances (up to 10,000 nodes), any systematic shortfall in subproblem quality would imply that both the proposed method and the baseline optimize over the same weak approximations, rendering the reported gap potentially attributable to tuning rather than PH decomposition itself.

    Authors: We agree that subproblem solution quality is central to interpreting the 5.28% gap. Because the baseline employs the identical destroy-and-repair, beam-search, and MIP subproblem solver, any consistent shortfall in subproblem quality affects both methods equally. The observed improvement therefore arises from the scenario-wise decomposition and the progressive hedging updates that coordinate investment decisions across scenarios, rather than from differences in subproblem solving. In the revision we will add direct evidence on smaller instances (where exact MIP solutions are tractable) showing that the integrated subproblem solver consistently returns solutions with small optimality gaps relative to the exact MIP optimum. This will confirm that both approaches operate on comparably high-quality subproblem solutions and that the reported gap is attributable to the PH coordination mechanism. revision: yes

  2. Referee: [§4 (subproblem solution procedure) and §5] No metrics are reported on subproblem optimality gaps, solution quality relative to exact MIP solves on smaller instances, or sensitivity to beam-search width and destroy-and-repair parameters. These omissions are load-bearing because the baseline already incorporates the identical integrated solver, so the incremental benefit of PH cannot be isolated without evidence that the subproblems are solved to comparable accuracy in both approaches.

    Authors: We acknowledge that explicit metrics on subproblem quality would strengthen the isolation of the PH benefit. In the revised manuscript we will report (i) optimality gaps returned by the MIP solver on the subproblems, (ii) solution-quality comparisons against exact MIP solves on smaller literature instances, and (iii) sensitivity results with respect to beam-search width and the destroy-and-repair parameters. These additions will demonstrate that the subproblems are solved to comparable accuracy under both the PH-based method and the baseline, thereby confirming that the 5.28% average improvement is due to the progressive hedging decomposition rather than parameter tuning. revision: yes

Circularity Check

0 steps flagged

No circularity: purely algorithmic heuristic with external baseline evaluation

full rationale

The paper describes a hybrid heuristic that decomposes the stochastic transmission expansion planning problem via progressive hedging and solves subproblems with a destroy-and-repair operator plus beam search and MIP. The central result is an empirical 5.28% average cost improvement over a non-trivial baseline that uses the identical integrated subproblem solver on the same adapted CATS instances. No equations, fitted parameters, or self-citations reduce the reported improvement to a quantity that is true by construction; the comparison is against an independent external baseline, and the method remains self-contained without any self-definitional or load-bearing self-referential steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper relies on standard mixed-integer programming formulations and established algorithmic components without introducing new free parameters, axioms, or postulated entities.

pith-pipeline@v0.9.0 · 5464 in / 1075 out tokens · 48707 ms · 2026-05-16T06:15:35.646149+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    The power grid library for benchmarking ac optimal power flow algorithms,

    S. Babaeinejadsarookolaee, A. Birchfield, R. D. Christie, C. Coffrin, C. DeMarco, R. Diao, M. Ferris, S. Fliscounakis, S. Greene, R. Huang, et al. The power grid library for benchmarking ac optimal power flow algorithms.arXiv preprint arXiv:1908.02788, 2019

    work page arXiv 1908

  2. [2]

    Bagheri, J

    A. Bagheri, J. Wang, and C. Zhao. Data-driven stochastic transmission expansion planning.IEEE Transactions on Power Systems, 32(5):3461– 3470, 2017

    work page 2017

  3. [3]

    Bezanson, A

    J. Bezanson, A. Edelman, S. Karpinski, and V . B. Shah. Julia: A fresh approach to numerical computing.SIAM Review, 59(1):65–98, Sept

    work page

  4. [4]

    doi: 10.1137/141000671

    work page doi:10.1137/141000671

  5. [5]

    Bienstock and A

    D. Bienstock and A. Verma. Strong np-hardness of ac power flows feasibility.Operations Research Letters, 47(6):494–501, 2019. ISSN 0167-6377

    work page 2019

  6. [6]

    Binato and G

    S. Binato and G. C. Oliveira. A reactive grasp for transmission network expansion planning. InEssays and Surveys in Metaheuristics, pages 81–100. Springer US, Boston, MA, 2002. ISBN 978-1-4615-1507-4

    work page 2002

  7. [7]

    Cadini, E

    F. Cadini, E. Zio, and C. Petrescu. Optimal expansion of an existing electrical power transmission network by multi-objective genetic algo- rithms.Reliability Engineering & System Safety, 95(3):173–181, 2010. ISSN 0951-8320

    work page 2010

  8. [8]

    E. da S. Oliveira, I. C. Silva Junior, L. W. de Oliveira, I. M. de Mendonc ¸a, P. Vilac ¸a, and J. T. Saraiva. A two-stage constructive heuristic algorithm to handle integer investment variables in transmission network expansion planning.Electric Power Systems Research, 192: 106905, 2021. ISSN 0378-7796

    work page 2021

  9. [9]

    L. L. Garver. Transmission network estimation using linear program- ming.IEEE Transactions on Power Apparatus and Systems, PAS-89(7): 1688–1697, 1970

    work page 1970

  10. [10]

    Lubin, O

    M. Lubin, O. Dowson, J. Dias Garcia, J. Huchette, B. Legat, and J. P. Vielma. JuMP 1.0: Recent improvements to a modeling language for mathematical optimization.Mathematical Programming Computation,

    work page

  11. [11]

    doi: 10.1007/s12532-023-00239-3

    work page doi:10.1007/s12532-023-00239-3

  12. [12]

    Lumbreras and A

    S. Lumbreras and A. Ramos. The new challenges to transmission expansion planning. survey of recent practice and literature review. Electric Power Systems Research, 134:19–29, 2016. ISSN 0378-7796

    work page 2016

  13. [13]

    Mahdavi, C

    M. Mahdavi, C. Sabillon Antunez, M. Ajalli, and R. Romero. Trans- mission expansion planning: Literature review and classification.IEEE Systems Journal, 13(3):3129–3140, 2019

    work page 2019

  14. [14]

    Morais, T

    R. Morais, T. Bulh ˜oes, and A. Subramanian. Exact and heuristic algorithms for minimizing the makespan on a single machine scheduling problem with sequence-dependent setup times and release dates.Euro- pean Journal of Operational Research, 315(2):442–453, 2024

    work page 2024

  15. [15]

    F. D. Munoz and J.-P. Watson. A scalable solution framework for stochastic transmission and generation planning problems.Computa- tional Management Science, 12(4):491–518, 2015

    work page 2015

  16. [16]

    P. S. Ow and T. E. Morton. Filtered beam search in scheduling†. International Journal of Production Research, 26(1):35–62, 1988

    work page 1988

  17. [17]

    Park and R

    H. Park and R. Baldick. Transmission planning under uncertainties of wind and load: Sequential approximation approach.IEEE Transactions on Power Systems, 28(3):2395–2402, 2013

    work page 2013

  18. [18]

    R. T. Rockafellar and R. J.-B. Wets. Scenarios and policy aggregation in optimization under uncertainty.Mathematics of operations research, 16(1):119–147, 1991

    work page 1991

  19. [19]

    Rosemberg, M

    A. Rosemberg, M. Tanneau, B. Fanzeres, J. Garcia, and P. Van Henten- ryck. Learning optimal power flow value functions with input-convex neural networks.Electric Power Systems Research, 235:110643, 2024. ISSN 0378-7796

    work page 2024

  20. [20]

    Silva Sousa and E

    A. Silva Sousa and E. N. Asada. Combined heuristic with fuzzy system to transmission system expansion planning.Electric Power Systems Research, 81(1):123–128, 2011. ISSN 0378-7796

    work page 2011

  21. [21]

    Soares, A

    A. Soares, A. Street, T. Andrade, and J. D. Garcia. An integrated progressive hedging and benders decomposition with multiple master method to solve the brazilian generation expansion problem.IEEE Transactions on Power Systems, 37(5):4017–4027, 2022

    work page 2022

  22. [22]

    Stott, J

    B. Stott, J. Jardim, and O. Alsac ¸. Dc power flow revisited.IEEE Transactions on Power Systems, 24(3):1290–1300, 2009

    work page 2009

  23. [23]

    Taylor, A

    S. Taylor, A. Rangarajan, N. Rhodes, J. Snodgrass, B. C. Lesieutre, and L. A. Roald. California test system (cats): A geographically accurate test system based on the california grid.IEEE Transactions on Energy Markets, Policy and Regulation, 2(1):107–118, 2024

    work page 2024

  24. [24]

    Valencia Zuluaga, A

    T. Valencia Zuluaga, A. Musselman, J.-P. Watson, and S. S. Oren. Parallel computing for power system climate resiliency: Solving a large- scale stochastic capacity expansion problem with mpi-sppy.Electric Power Systems Research, 235:110720, 2024. ISSN 0378-7796

    work page 2024

  25. [25]

    M. C. V ´elez-Gallego, J. Maya, and J. R. Montoya-Torres. A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan.Computers & Operations Research, 73:132–140, 2016

    work page 2016

  26. [26]

    Watson and D

    J.-P. Watson and D. L. Woodruff. Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems. Computational Management Science, 8(4):355–370, 2011

    work page 2011