Algorithmes heuristiques et exacts pour le problème de l’ensemble dominant connexe minimum

Abstract

Dans ce mémoire, nous abordons le problème de l’ensemble dominant connexe de cardinalité minimale. Nous nous penchons, en particulier, sur le développement de méthodes pour sa résolution basées sur la programmation par contraintes et la programmation en nombres entiers. Nous présentons, en l’occurrence, une heuristique et quelques méthodes exactes pouvant être utilisées comme heuristiques si on limite leur temps d’exécution. Nous décrivons notamment un algorithme basé sur l’approche de décomposition de Benders, un autre combinant cette dernière avec une stratégie d’investigation itérative, une variante de celle-ci utilisant la programmation par contraintes, et enfin une méthode utilisant uniquement la programmation par contraintes. Des résultats expérimentaux montrent que ces méthodes sont efficaces puisqu’elles améliorent les méthodes connues dans la littérature. En particulier, la méthode de décomposition de Benders avec une stratégie d’investigation itérative fournit les résultats les plus performants.

In this work, we address the minimum connected dominating set problem. We focus, in particular, on the development of solution methods based on constraint programming and integer programming, including one heuristic and some exact methods that can be used as heuristics if we limit their running time. These are based on Benders decomposition and exploit a stand-alone and an iterative probing strategy. In particular, we develop a method based on the stand-alone Benders decomposition, another combining this one with an iterative probing strategy, a variant of the latter using constraint programming, and finally, a method using only constraint programming. Experimental results show that these methods are effecient, since they perform better than those known in the literature. In particular, iterative probing Benders decomposition provides the best results overall.