Measuring Smart Grids: Optimal Placement of Sensors in Power Grids by Leo Liberti

Within the "SO-grid" French smart grid pilot project, we were confronted with the problem of placing a minimum number of sensors on the links of a power grid, such that voltage and power is measured at all nodes. This differs from vertex cover because Ohm's and Kirchoff's laws induce a propagation-based notion of observability: a node is observed if certain other close nodes are observed. We first provide a natural but computationally unsatisfactory MILP model, which we then reformulate to a bilevel MILP via a fixed-point modelling of the iterative observability notion. We turn this bilevel problem to a single-level MILP with fewer variables than the original one. We then propose a fast row-generation algorithm for the bilevel problem, and show how it generalizes to a large class of bilevel MILPs.