EURO 2025 Leeds
Abstract Submission

2032. On the Complexity of the Switch Allocation Problem in Power Distribution Networks

Invited abstract in session MD-46: Planning and operation of power networks, stream Energy Economics & Management.

Monday, 14:30-16:00
Room: Newlyn 1.07

Authors (first author is the speaker)

1. Fábio Usberti
Institute of Computing, Universidade Estadual de Campinas
2. José Federico Vizcaino González
UNESP/Guaratinguetá
3. Laura Silva Assis
Computer Engineering, CEFET/RJ Petrópolis
4. Celso Cavellucci
UNICAMP

Abstract

The Switch Allocation Problem (SAP) is central to optimizing reliability in power distribution networks, where the strategic placement of sectionalizing switches significantly reduces the expected Energy Not Supplied (ENS). Despite extensive research into SAP and its variants, the fundamental complexity of the Sectionalizing Switch Allocation Problem (SSAP), specifically whether it is NP-hard, remained unresolved. Historically, the SSAP was predominantly addressed through heuristics or exact algorithms based on Integer Linear Programming (ILP), both approaches having limitations. Heuristic methods offer approximate solutions without guaranteeing optimality, whereas previous exact approaches using ILP or dynamic programming (DP) encountered exponential complexity, restricting scalability.

This work conclusively resolves this open complexity question by introducing the first exact polynomial-time dynamic programming algorithm capable of optimally solving SSAP instances efficiently. Our algorithm employs a carefully defined state space and optimality functions tailored for both linear and branched radial networks. By establishing polynomial-time solvability, this research addresses a longstanding open problem in combinatorial optimization for power systems and lays a robust foundation for future advancements in distribution network reliability optimization.

Keywords

Status: accepted

Back to the list of papers