PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial-time algorithms for setting tight big-M coefficients in transmission expansion planning with disconnected buses

Behnam Jabbari-Marand, Adolfo R. Escobedo

arXiv:2609.09474v1cs.DM

TL;DR

TEP is growing more complex with renewable integration and rising demand, while tight bounds for disconnected bus pairs are difficult to derive efficiently. The paper introduces LSPC to identify relevant paths for big-M bounds; its path-based valid inequalities dominate those derived using the longest path problem or larger initial bounds.

  • Problem

    For disconnected bus pairs, identifying paths needed for tight big-M bounds is difficult because existing approaches generally rely on the NP-hard longest path problem.

    Source: §1 · p. 2

  • Method

    LSPC uses structural properties of expansion settings to identify relevant paths and derive tight voltage-angle-difference upper bounds for disconnected bus pairs.

    Source: §4.1 · p. 8, §5 · p. 13

  • Results

    LSPC-initialized path-based valid inequalities dominate those derived using the longest path problem or any larger initial bound.

    Source: §4.1 · p. 11, §5 · p. 13

  • Takeaways & Limitations

    For the stated new-bus integration settings, LSPC provides a polynomial-time alternative to the longest path problem for deriving tight bounds.

    Source: §5 · p. 13

    The modeling framework assumes one existing or candidate line per corridor, and the stated rooted-subnetwork setting is separated from the initial network by a single expansion corridor.

    Source: §2 · p. 2, §3 · p. 5

Abstract

from arXiv · show

The increasing penetration of renewable energy and rising electricity demand are driving the need to integrate new buses and transmission lines into transmission grids. These trends are reshaping transmission expansion planning (TEP), motivating the development of effective methodologies to manage the resulting complexity. This paper introduces the longest shortest-path connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of TEP using valid inequalities (VIs). Traditional approaches for determining big-M coefficients in disconnected TEP networks typically rely on solving the computationally intensive longest path problem (LPP). In contrast, LSPC circumvents these limitations by efficiently identifying relevant power-flow paths between disconnected buses within the expansion network. We demonstrate that the VIs generated from these identified paths dominate those derived from LPP-based methods and other existing approaches.

1 Introduction

TEP planning is becoming more complex as demand and renewable integration grow, while exact DC-TEP methods face computational challenges. The paper proposes strengthening the MILP formulation by efficiently identifying relevant paths to derive tight big-M bounds for disconnected bus pairs.

1 Introduction

  • DC-TEP’s MILP is NP-hard, and existing exact approaches face scalability challenges through high computational cost or slow convergence on large problems.Metaheuristics and other inexact methods do not formally guarantee solution quality.Source: §1 · p. 2
  • Tightening big-M bounds can strengthen DC-TEP’s MILP formulation, since overly large values weaken the LP relaxation and increase exact-method computational burden.Prior bound-strengthening work has focused on already-connected networks or used computationally intractable procedures.Source: §1 · p. 2
  • The paper exploits structural properties of restricted but practically relevant expansion settings to identify paths and efficiently derive tight big-M bounds without solving the NP-hard longest path problem.The introduction identifies relevant power-flow paths between bus pairs as the basis for deriving these bounds.Source: §1 · p. 2

2 Modeling framework and background

The paper sets out a DC-TEP model and reviews how path-based angle-difference bounds can strengthen its disjunctive formulation. Existing-path methods do not cover prospective new-bus subnetworks, where connectivity can depend on expansion decisions and path enumeration can become intractable.

2 Modeling framework and background

  • Each corridor is assumed to contain at most one existing or candidate line, and the framework distinguishes established corridors from expansion corridors.Buses represent connection points for electrical components, and corridors are transmission pathways between buses.Source: §2 · p. 2

Parameters

  • The parameters describe line-installation and generation costs, generation limits and demand, angle-difference limits, line capacities, reactance, and a cost-scaling factor; variables include flows, generation, voltage angles, and line-purchase decisions.The listed parameters and variables define the model’s investment and operating quantities.Source: Parameters · p. 2, Variables · p. 3

2.2 MILP disjunctive formulation of DC-TEP

  • The single-investment-period MILP disjunctive model minimizes line and generation costs, enforces flow balance and line capacities, and uses disjunctive constraints for candidate lines.The disjunctive parameter must be large enough to preserve integer-feasible solutions but as small as possible to strengthen LP relaxations.Source: §2.2 · p. 3, §2.3 · p. 3

2.3 Review of TEP formulation improvement approaches

  • For connected bus pairs, summing angle-difference inequalities along an established path bounds their angle difference; shortest-path methods select the tightest such bound.The review describes extensions that derive bounds for any bus pair connected in the existing network.Source: §2.3 · pp. 4–5
  • Existing-path techniques do not apply to prospective new-bus subnetworks, where expansion decisions determine connectivity and candidate-path combinations can grow combinatorially.The review notes that enumerating all simple candidate paths for disconnected pairs is equivalent to an NP-hard longest path problem.Source: §2.3 · p. 5

3 Importance of the longest shortest-path

For disconnected bus pairs in transmission expansion, longest-path bounds can be computationally difficult and overly conservative. LSPC focuses on relevant connections by joining candidate tie lines to shortest paths through the existing grid.

3 Importance of the longest shortest-path

  • LPP-based methods require solving an NP-hard longest path problem, and their bounds can exceed plausible power-flow paths in large meshed grids.The resulting bounds can be overly conservative.Source: §3 · p. 5
  • The approach targets practical settings where new buses form relatively simple expansion trees connected to the existing grid through a small number of candidate tie lines.An expansion tree is an acyclic, connected subgraph rooted at a bus separated from G0 by one expansion corridor.Source: §3 · p. 5
  • Path-based VIs require a validity condition absent from the original expression; without it, they may exclude integer-feasible solutions.The paper also states that VIs initialized with LPP-based bounds are dominated by corresponding VIs using the proposed bounds.Source: §3 · p. 6
  • In highly connected existing grids, shorter relevant connections can avoid the unnecessary and ineffective LPP, while LSPC focuses on paths relevant to each disconnected pair.The paper cites an average bus degree of about 2.5 in large-scale power systems [33].Source: §3 · pp. 6–7
  • LSPC evaluates connections between neighboring buses, links them with shortest paths through G0, and selects the longest resulting connection as the bound.Each full path merges shortest-path subpaths with candidate connections at the original buses.Source: §3 · pp. 6–7
  • Unlike graph diameter, which can yield overly conservative estimates on the expansion graph, LSPC considers only the graph region relevant to the specific disconnected pair.The diameter can include shortest paths between buses that may not be constructed.Source: §3 · p. 7

4 The longest shortest-path connection algorithm

This section presents LSPC for tightening angle-difference bounds between disconnected bus pairs using paths formed from existing-grid connections and expansion-tree structure. It describes Phase I’s shortest-path searches and conditions, followed by Phase II’s combination of bounds through intermediary buses, and addresses tightness, dominance over LPP-based inequalities, and complexity.

4.1 LSPC Phase I: Root-bus integration

  • 6 versus 4: in the illustrated case, LPP’s path weighs 6, while LSPC’s selected connection weighs 4, making the LPP path 1.5 times longer.Both methods select the same tie lines, but LPP links them through the longest path in G, whereas LSPC uses a shortest path in G0.Source: Figure 6 · p. 8, §4.1 · p. 8
  • Phase I forms candidate paths by linking reachable neighboring buses through shortest paths in G0, adding terminal expansion corridors, and selecting the longest connection to set the bound.When a bus already connects to the initial grid, refining the reachability set preserves necessary connections while avoiding restrictive redundant corridor requirements.Source: §4.1 · pp. 8–9
  • Under its connectivity condition, Phase I’s longest shortest-path connection gives the tightest attainable path-based angle-difference bound and is exact when corridor-construction information is unavailable.The condition requires every refined reachability-set pair other than [i, j] to be connected in G0.Source: §4.1 · pp. 10–11
  • The VI built from LSPC’s selected path dominates LPP-based VIs and those using any initial bound greater than the selected path’s weight.The comparison applies over the region where the absolute angle difference is at least the candidate path’s weight.Source: §4.1 · p. 11
  • O(m log n) is the time complexity of Phase I under the stated exponential degree-tail assumption.Here n is the number of buses and m is the number of existing and candidate lines.Source: §4.1 · p. 11
  • Phase I runs Dijkstra searches from the lower-degree bus’s neighbors and connects each neighbor pair; its complexity is O(min{deg(i), deg(j)} m log n + deg(i) deg(j)), or O(m log n) under effectively O(1) practical-grid bus degrees.The searches run in G0, and terminal lines are appended to form each connection.Source: §4.1 · p. 11

4.2 LSPC Phase II: Tree-structured bus integration

  • Phase II extends Phase I bounds from a tree’s root along its unique tree paths, combining bounds through intermediary buses to connect disconnected pairs involving deeper expansion-tree buses.It applies when bounds from each disconnected bus to an intermediary λ have already been identified.Source: §4.2 · pp. 12–13
  • When multiple intermediary buses are available, Phase II selects the smallest combined bound, avoiding non-simple paths and enabling iterative connections to deeper tree buses.The bound combines θiλ and θλj when both are below γ.Source: §4.2 · pp. 12–13

5 Conclusion

The paper introduces LSPC to derive tight voltage-angle-difference bounds for disconnected bus pairs in relatively simple new-bus subnetworks, without solving the longest path problem. It reports that LSPC-initialized path-based valid inequalities dominate those based on LPP or any larger initial bound.

5 Conclusion

  • LSPC derives tight angle-difference bounds for disconnected bus pairs in relatively simple new-bus subnetworks in polynomial time.The paper reports that its LSPC-initialized path-based valid inequalities dominate those derived from LPP or any larger initial bound.Source: §5 · p. 13

Data availability

The article does not contain any datasets.

Data availability

Appendix A

Appendix A defines candidate paths for the path-based valid inequalities and notes a condition needed to preserve validity. It also specifies how the corridor indicator is evaluated.

Appendix A

  • Candidate path ρij connects buses i and j in G and includes at least one expansion corridor; Ne(ρij) counts those corridors.Source: Appendix A · p. 13
  • Indicator Ikl equals 1 when corridor (k,l) belongs to both ρij and Ω1, and 0 otherwise.Source: Appendix A · p. 13
  • When w(ρij) exceeds θij and ν>1, inequality (19) becomes invalid and may exclude integer-feasible solutions.Source: Appendix A · p. 13

Appendix B

Appendix B compares path-based valid inequalities initialized with the LSPC bound against those based on LPP or larger initial bounds. It establishes LSPC-based dominance within the effective comparison region.

Appendix B

  • The comparison concerns |θi−θj|≥w(ρij), where the path-based inequality can enforce an angle-difference bound.Source: Appendix B · p. 13
  • Within the effective domain, LPP-based inequalities are dominated by LSPC-based angle-difference inequalities or path-based inequalities initialized with the LSPC bound.Source: Appendix B · pp. 13–14
Loading 2609.09474v1…