A polynomial-time exact algorithm for the sectionalizing switch allocation problem

The allocation of switches in power distribution networks is a critical combinatorial optimization problem concerning reliability optimization. In this work, we consider a set of sectionalizing switches and a radial network, for which the objective is to find the best edges to allocate the switches to minimize the expected energy not supplied. An open question in the literature concerns the computational complexity of this fundamental problem, specifically, whether it is NP-hard. In this paper, we show that it is in fact tractable by presenting the first exact polynomial-time algorithm, based on dynamic programming. We compare our approach with previous state-of-the-art methodologies. Extensive computational experiments show that the proposed dynamic programming scales much better than the previous approach. Large instances, with more than three thousand nodes, are solved for the first time for any number of switches.