The capacitated spanning forest problem

Davidescu, George (2020) The capacitated spanning forest problem. Advisor: Caldarelli, Prof. Guido. pp. 128. [IMT PhD Thesis]

Text (Doctoral thesis) Davidescu_phdthesis.pdf - Published Version Available under License Creative Commons Attribution Non-commercial Share Alike. Download (5MB)

Abstract

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.

Item Type:	IMT PhD Thesis
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
PhD Course:	Complex networks
Identification Number:	10.6092/imtlucca/e-theses/304
NBN Number:	urn:nbn:it:imtlucca-27326
Date Deposited:	26 Mar 2020 16:31
URI:	http://e-theses.imtlucca.it/id/eprint/304

Actions (login required, only for staff repository)

View Item