Treffer: Integer linear programs for the power dominating set problem with channel limitation.

The power dominating set problem (PDS) is a graph optimization problem with applications related to the control and monitoring of electric power systems using devices called phasor measurement units (PMUs). The objective of PDS is to find a minimum set of vertices on which to install PMUs that allow monitoring all remaining vertices by recursively applying two observation rules. In particular, the domination rule assumes that a vertex with a PMU can monitor all its neighbors. In real-world applications, PMUs have a predefined number of channels that limit the number of neighbors that they can monitor. This work proposes a novel integer linear programming formulation for the PDS variant that considers PMUs with channel limitation. The formulation is based on a set of constraints to forbid circular precedences that might arise in the application of the observation rules. As the number of constraints grows exponentially, an algorithm is developed to handle them dynamically (as lazy constraints) with an efficient separation routine. Computational experiments are performed on benchmark instances with up to 13.659 vertices to compare the performance of the new formulation with others adapted from the PDS literature. An interesting behavior is observed, where the best-performing formulation strongly depends on the number of limited channels. In particular, the new formulation is effective in instances with moderate channel limitation. [ABSTRACT FROM AUTHOR]