Tackling combinatorial optimization with Hybrid DQL: A case study with the Minimum Dominating Set Problem

This paper proposes combining reinforcement learning -- specifically, deep Q--learning -- with a local search procedure to tackle NP-hard combinatorial optimization problems. We select the Minimum Dominating Set problem, a classic combinatorial optimization problem from Graph Theory, to assess the proposed approach. Each model was trained on graphs sampled from a fixed Erdős–Rényi G(n, p) distribution, and the ground truth solutions for the minimization problem were computed via Integer Linear Programming with the Gurobi Optimizer. We report results in terms of average optimization ratios and the average sizes of the produced solutions. Additionally, a greedy algorithm was implemented to serve as a performance baseline. Our findings indicate that the Deep Q-Network alone was insufficient to discover optimal solutions; however, when combined with the local search procedure, the proposed method achieved competitive performance on small graph instances.