A flow-based heuristic algorithm for network operations planning in smart grids

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Research units

  • St. Petersburg National Research University of Information Technologies, Mechanics and Optics (ITMO)
  • IMT School for Advanced Studies Lucca
  • Luleå University of Technology


The smart grid is envisioned as a reconfigurable energy exchange network that is resilient to failures. An expected feature of the future smart grid is optimal power distribution from energy producers to consumers, also referred to as network operation planning. This entails allocating finite energy resources to customers in order to optimally satisfy all customer demands, subject to constraints on the topology of the graph. We model this problem as the Capacitated Spanning Forest Problem (CSF), namely the optimization problem of creating a spanning forest with a capacity constraint on each tree limiting its total weight. We present a new heuristic algorithm for solving CSF based on computing the minimum-cost maximum flow on the graph. Our algorithm outperforms state of the art approaches with respect to solution quality and running time.


Original languageEnglish
Title of host publicationProceedings of the 44th Annual Conference of the IEEE Industrial Electronics Society, IECON 2018
Publication statusPublished - 26 Dec 2018
MoE publication typeA4 Article in a conference publication
EventAnnual Conference of the IEEE Industrial Electronics Society - Washington, United States
Duration: 21 Oct 201823 Oct 2018
Conference number: 44

Publication series

NameProceedings of the Annual Conference of the IEEE Industrial Electronics Society
ISSN (Print)1553-572X


ConferenceAnnual Conference of the IEEE Industrial Electronics Society
Abbreviated titleIECON
CountryUnited States

    Research areas

  • computational complexity, graph theory, optimisation, power system planning, resource allocation, smart power grids

ID: 32397583