Prof. Diego Delle Donne, ESSEC Business School France
Chair: Prof. Claudia Archetti, University of Brescia
When: Thursday, October 23rd, 2025, 10 AM
Where: Sala della Biblioteca, Via San Faustino 74/B
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 PDS and for its 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. We show that the new formulation is competitive in the classical PDS and it is very effective in the channel-limited variant of PDS, outperforming formulations based on existing approaches from the PDS literature. This is a joint work with Mauro Lucci and Mariana Escalante from Universidad Nacional de Rosario, Argentina.