The Power Edge Set problem

The automated real time control of an electrical network is achieved through the estimation of its state using Phasor Measurement Units (PMUs). Given an undirected graph representing the network, we study the problem of finding the minimum number of PMUs to place on the edges such that the graph is fully observed. This problem is also known as Power Edge Set problem, a variant of the Power Dominating Set problem. This problem is naturally modelled using an iteration indexed binary linear program, which turns out to be too large for practical purposes. We use a fixed-point argument to remove the iteration indices, and obtain a more compact bilevel formulation. We then reformulate the latter to a single-level mixed-integer linear program, which performs better than the natural formulation. We then go on to provide an algorithm that solves the bilevel program much faster than an off-the-shelf solver can solve the previous models. We also discuss conventional measures and robust variants of the problem. We then propose a natural generalization, which can also be cast as a bilevel formulation, and solved using a similar methodology.



View The Power Edge Set problem