Optimization Online


The Power Edge Set problem

Pierre-Louis Poirion (poirion***at***lix.polytechnique.fr)
Sonia Toubaline (toubaline***at***lix.polytechnique.fr)
Claudia D'Ambrosio (dambrosio***at***lix.polytechnique.fr)
Leo Liberti (liberti***at***lix.polytechnique.fr)

Abstract: 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.

Keywords: Real time electrical network monitoring, Bilevel program, Mixed integer linear program, PMU placement problem

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 09/28/2015
Entry Accepted: 09/28/2015
Entry Last Modified: 07/13/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society