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.

A new framework for conflict-free coloring of hypergraphs is presented, leading to a novel graph problem which generalizes the partition and the list coloring problems, well-known for their multiple applications. Two integer linear programming formulations are proposed for this problem: a compact formulation inspired by the pioneering formulation for the vertex coloring problem and a set covering formulation whose variables are associated with stable sets. For the latter formulation, a branch-and-price algorithm is developed. Computational experiments in random instances validate the superiority of this approach over the direct solution of the compact formulation with a commercial solver.