The capacitated spanning forest problem

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 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. This thesis deals with modeling 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. I prove the NP-completeness of this problem and provide three different heuristic algorithms for solving it: a Local Search heuristic, a Hill Climbing heuristic, and a Max Flow-based heuristic, each of which has been published in a peer-reviewed IEEE conference. These are the first algorithmic approaches in the literature addressing this problem. Each algorithm is an improvement over the previous in solution quality and efficiency. Using a simulation-based approach I empirically demonstrate the suitability of these algorithms for planning the initial configuration of a smart grid’s topology, and for recovery when faults occur.