Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem

• Ano de defesa: 2023
• Autor(a) principal: Silva, Mateus Carvalho
• Orientador(a): Melo, Rafael Augusto de
• Banca de defesa: Melo, Rafael Augusto , Silva, Pedro Henrique Gonzáles , Durão, Frederico Araújo , Resende, Maurício Guilherme de Carvalho
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal da Bahia
• Programa de Pós-Graduação: Programa de Pós-Graduação em Ciência da Computação (PGCOMP)
• Departamento: Instituto de Computação - IC
• País: Brasil
• Palavras-chave em Português: Otimização combinatória; Coloração de grafos; Número de Grundy; BRKGA; Análise de pior caso
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufba.br/handle/ri/39322

Given a graph G, its Grundy number Γ(G) defines the worst-case behavior for the wellknown and widely used first-fit greedy coloring heuristic. Specifically, Γ(G) is the largest k for which a k-coloring can be obtained with the first-fit heuristic. The connected Grundy number Γc(G) gives the worst-case behavior for the connected first-fit coloring heuristic, that is, one in which each vertex to be colored, except the first, is added adjacent to an already colored vertex. Both problems are NP-hard. In this master’s thesis, we present heuristic and exact approaches to the Grundy coloring problem and the connected Grundy coloring problem, which are optimization problems consisting of obtaining the Grundy number and the connected Grundy number, respectively. This study proposes the use of a algorithm Biased Random-Key Genetic Algorithm (BRKGA) and the use of integer programming formulations using a more traditional (standard) approach and a representative one. A new combinatorial upper bound is also proposed that is valid for both problems and an algorithm using dynamic programming for its calculation. The computational experiments show that the new upper bound can improve over a well-established combinatorial bound available in the literature for several instances. The results also evidence that the formulation by representatives has an overall superior performance than the standard formulation, achieving better results for the denser instances, while the latter performs better for the sparser ones to the Grundy coloring problem. However, we show that these types of integer programming formulations are computationally impractical for the connected version. Furthermore, the BRKGA can find high-quality solutions for both problems and can be used with confidence in large instances where the formulations fail for the Grundy coloring problem.