Electrical flows over spanning trees
From MaRDI portal
spectral sparsificationapproximation algorithmsiterative roundingelectrical flowsdistribution network reconfiguration
Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Applications of mathematical programming (90C90) Deterministic network models in operations research (90B10) Combinatorial optimization (90C27) Nonlinear programming (90C30) Mixed integer programming (90C11)
Abstract: The network reconfiguration problem seeks to find a rooted tree such that the energy of the (unique) feasible electrical flow over is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from for general graphs, to over grids with uniform resistances on edges, and for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance.
Recommendations
- A Steiner arborescence model for the feeder reconfiguration in electric distribution networks
- Graphical models for optimal power flow
- A polynomial algorithm for deciding the validity of an electrical distribution tree
- Optimisation of electrical network configuration: complexity and algorithms for ring topologies
- Partition on trees with supply and demand: kernelization and algorithms
Cites work
- scientific article; zbMATH DE number 4064516 (Why is no real title available?)
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees
- A Separator Theorem for Planar Graphs
- A cycle-based formulation and valid inequalities for DC power transmission problems with switching
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra
- An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
- Approximating minimum bounded degree spanning trees to within one of optimal
- Balancing minimum spanning trees and shortest-path trees
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Convex Relaxation of Optimal Power Flow—Part I: Formulations and Equivalence
- Disjoint paths in graphs
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Exact Convex Relaxation of Optimal Power Flow in Radial Networks
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Faster energy maximization for faster maximum flow
- Graph sparsification by effective resistances
- Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
- Linear models. Least squares and alternatives
- Lower-stretch spanning trees
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Minimizing Lipschitz-continuous strongly convex functions over integer points in polytopes
- Network flow algorithms
- Probability on trees and networks
- Provisioning a virtual private network: a network design problem for multicommodity flow
- Sampling random spanning trees faster than matrix multiplication
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Spectral sparsification of graphs
- Using petal-decompositions to build a low stretch spanning tree
- Using separation algorithms to generate mixed integer model reformulations
Cited in
(8)- A polynomial algorithm for deciding the validity of an electrical distribution tree
- Configuring an heterogeneous smartgrid network: complexity and approximations for tree topologies
- A Steiner arborescence model for the feeder reconfiguration in electric distribution networks
- A new approach to computing maximum flows using electrical flows
- Special issue: Global solution of integer, stochastic and nonconvex optimization problems
- Graphical models for optimal power flow
- Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network
- Location of Protection Devices on Electrical Tree Networks
This page was built for publication: Electrical flows over spanning trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097649)
