Meta-Heurísticas e programação linear inteira para o problema da dominação romana tripla em grafos

Abstract

The Triple Roman Domination Problem is a combinatorial optimization problem defined as follows. Given a graph G and a function h :V(G) → {0,1,2,3,4}, we say that v ∈V(G) is active if h(v) > 0. The active neighborhood of v is the set of active neighbors of v and is denoted by AN(v). A triple Roman domination function (TRDF) of a graph G is a function h : V(G) → {0,1,2,3,4} such that, for every vertex v ∈ V(G), it holds that ∑u∈N[v] h(u) ≥ 3+|AN(v)|. The weight of h is the value ∑v∈V(G) h(v). Given a graph G, the triple Roman domination number of G, γ3R(G), is the smallest possible weight of a TRDF of G. The goal of the triple Roman domination problem is to find γ3R(G). This problem has already been proven to be NP-complete and has applications in military contexts, resource allocation, and server placement. This work proposes the first two metaheuristics for the problem, based on Genetic Algorithms and Ant Colony Optimization, and presents the first correct Integer Linear Programming formulation for the problem in the literature. Additionally, we discuss the flaws of an existing formulation. The comparison between the algorithms was conducted based on three main criteria: (i) execution time, measured in seconds, to evaluate the computational efficiency of each approach; (ii) solution quality, analyzed through the fitness value, comparing the results of the metaheuristics with the optimal solutions obtained by ILP; and (iii) relative gap, a metric that measures the proximity of the heuristic solutions to the global optimum provided by ILP, calculated based on the best solution found by any metaheuristic. These criteria ensure a reliable evaluation of the effectiveness and efficiency of the proposed approaches.