The capacitated spanning forest problem

The smart grid is envisioned as a reconfigurable energy exchangenetwork that is resilient to failures. An expected featureof the future smart grid is optimal power distributionfrom energy producers to consumers, also referred to as networkplanning. This entails allocating finite energy resourcesto customers in order to optimally satisfy all customer demands,subject to constraints on the topology of the graph.This thesis deals with modeling this problem as the CAPACITATEDSPANNING FOREST PROBLEM (CSF), namely the optimizationproblem of creating a spanning forest with a capacityconstraint on each tree limiting its total weight. I prove theNP-completeness of this problem and provide three differentheuristic algorithms for solving it: a Local Search heuristic, aHill Climbing heuristic, and a Max Flow-based heuristic, eachof which has been published in a peer-reviewed IEEE conference.These are the first algorithmic approaches in the literatureaddressing this problem. Each algorithm is an improvementover the previous in solution quality and efficiency. Usinga simulation-based approach I empirically demonstratethe suitability of these algorithms for planning the initial configurationof a smart grid’s topology, and for recovery whenfaults occur.