PhD Student

• mathematical optimisation
• mathematical modelling
• combinatorics
• numerical analysis
• algorithms

Working Title: On the structure of combinatorial problems related to resilience improvements in electricity grids

Many optimisation problems related to the resilience, robustness or reliability of power systems have a combinatorial nature that leads to high computational complexity. While basic theoretical analysis often easily shows that such problems are NP-hard, deeper investigations reveal even more restrictive properties, such as Poly-APX-hardness or, in some cases, even NPO-completeness. These characteristics suggest that, in general, finding efficient algorithms to solve these problems exactly or even approximately is unlikely — unless it is proven that P = NP.

To tackle this challenge, our research focuses on identifying structural properties of these problems and power systems themselves. By leveraging these properties, we aim to restrict the general case to realistic scenarios where efficient solutions are possible.

In particular, we have discovered that medium-voltage grids often exhibit a structural sparseness characterised by low treewidth. This discovery allowed us to address the problem of distribution service restoration in microgrids (DSRM).

The DSRM problem is a critical aspect of power system resilience, involving the restoration of electricity to as many customers as possible within a city after a complete blackout. This must be achieved using the distributed energy resources installed in the grid itself. In its general form, this problem was proven by us to be NPO-complete.

Nonetheless, by exploiting the low treewidth of distribution grids and other structural properties of DSRM, we developed a polynomial-time heuristic that provides a provably feasible solution for it when restricted to realistic instances. To the best of our knowledge, our algorithm is the first ever to achieve both polynomial runtime and guaranteed feasibility for the DSRM problem.