Integer Programming algorithms for the Domatic Partitioning Problem

This work proposes a new integer programming formulation based on the representative’s concept and a Branch-and-Price algorithm for the Domatic Partitioning Problem (DPP), which is a variant of the classical dominating set problem in graphs. In the literature, the DPP has been used as a model to extend the lifetime of wireless sensor networks. A comparison with the formulation presented in the literature shows that the representative formulation outperforms the literature formulation for high-density random graphs. Furthermore, it is shown that the Branch-and-Price algorithm has a better behavior over all formulations. This is the first proposal of Branch-and-Price for the DPP. A new SUBMIPping matheuristic with robust local branching cuts is also proposed here.