Capacitated power dominating set problem: a solution approach based on forbidden propagation sets
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916023119118336 |
|---|---|
| author | Lucci, Mauro Donne, Diego Delle Escalante, Mariana |
| author_facet | Lucci, Mauro Donne, Diego Delle Escalante, Mariana |
| contents | The optimal placement of measurement devices in electrical power systems is commonly modeled through the power dominating set problem. However, in real-world applications, these devices have limited capacities, leading to a capacitated variant of the problem that has received little attention in the literature. In this work, we introduce forbidden propagation sets, novel combinatorial structures that cannot occur simultaneously in any feasible solution. This notion enables a new class of integer linear programming formulations. They combine infection-based variables with exponentially many constraints, while avoiding big-$M$ constraints. We derive structural properties, valid inequalities, and redundancy-breaking constraints, and design an efficient lazy-separation procedure based on cycle detection. Computational experiments on benchmark instances with up to 14,000 vertices show that the proposed method achieves an average execution-time improvement of 1.7x over existing approaches adapted from the literature. Moreover, the results indicate that performance depends not only on network size, but also on capacities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_18533 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Capacitated power dominating set problem: a solution approach based on forbidden propagation sets Lucci, Mauro Donne, Diego Delle Escalante, Mariana Optimization and Control Discrete Mathematics The optimal placement of measurement devices in electrical power systems is commonly modeled through the power dominating set problem. However, in real-world applications, these devices have limited capacities, leading to a capacitated variant of the problem that has received little attention in the literature. In this work, we introduce forbidden propagation sets, novel combinatorial structures that cannot occur simultaneously in any feasible solution. This notion enables a new class of integer linear programming formulations. They combine infection-based variables with exponentially many constraints, while avoiding big-$M$ constraints. We derive structural properties, valid inequalities, and redundancy-breaking constraints, and design an efficient lazy-separation procedure based on cycle detection. Computational experiments on benchmark instances with up to 14,000 vertices show that the proposed method achieves an average execution-time improvement of 1.7x over existing approaches adapted from the literature. Moreover, the results indicate that performance depends not only on network size, but also on capacities. |
| title | Capacitated power dominating set problem: a solution approach based on forbidden propagation sets |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2605.18533 |