Configuring an heterogeneous smartgrid network: complexity and approximations for tree topologies

Dominique Barth (), Thierry Mautor (), Dimitri Watel () and Marc-Antoine Weisser ()
Additional contact information
Dominique Barth: University of Versailles-St Quentin
Thierry Mautor: University of Versailles-St Quentin
Dimitri Watel: ENSIIE
Marc-Antoine Weisser: Paris-Saclay University

Journal of Global Optimization, 2024, vol. 89, issue 1, No 10, 223-257

Abstract: Abstract We address the problem of configuring a power distribution network with reliability and resilience objectives by satisfying the demands of the consumers and saturating each production source as little as possible. We consider power distribution networks containing source nodes producing electricity, nodes representing electricity consumers and switches between them. Configuring this network consists in deciding the orientation of the links between the nodes of the network. The electric flow is a direct consequence of the chosen configuration and can be computed in polynomial time. It is valid if it satisfies the demand of each consumer and capacity constraints on the network. In such a case, we study the problem of determining a feasible solution that balances the loads of the sources, that is their production rates. We use three metrics to measure the quality of a solution: minimizing the maximum load, maximizing the minimum load and minimizing the difference of the maximum and the minimum loads. This defines optimization problems called respectively $$\min $$ min -M, $$\max $$ max -m and $$\min $$ min -R. In the case where the graph of the network is a tree, it is known that the problem of building a valid configuration is polynomial. We show the three optimization variants have distinct properties regarding the theoretical complexity and the approximability. Particularly, we show that $$\min $$ min -M is polynomial, that $$\max $$ max -m is NP-Hard but belongs to the class FPTAS and that $$\min $$ min -R is NP-Hard, cannot be approximated to within any exponential relative ratio but, for any $$\varepsilon > 0$$ ε > 0 , there exists an algorithm for which the value of the returned solution equals the value of an optimal solution shifted by at most $$\varepsilon $$ ε .

Keywords: Complexity; Approximability; Electrical network flow; Tree topology (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-023-01338-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:89:y:2024:i:1:d:10.1007_s10898-023-01338-0

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-023-01338-0

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().