Exact and Heuristic Approaches to the Maximum Capacity Representatives Problem

  • Italos Estilon da Silva de Souza
  • Mauro Roberto Costa da Silva
  • Welverton Rodrigues da Silva
  • Rafael C. S. Schoeury

Resumo


This paper approaches the problem of finding the system of representatives of a family of disjoint sets. To solve this problem, three methods were used: integer programming, branch-and-bound, and the BRKGA metaheuristic. We observed that, in randomly generated instances, the branch-and-bound algorithm was the best exact method but it was surpassed by BRKGA for large instances.

Publicado
26/07/2018
DE SOUZA, Italos Estilon da Silva; DA SILVA, Mauro Roberto Costa; DA SILVA, Welverton Rodrigues; SCHOEURY, Rafael C. S.. Exact and Heuristic Approaches to the Maximum Capacity Representatives Problem. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3164.