Exact and Heuristic Approaches to the Maximum Capacity Representatives Problem

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

DOI: https://doi.org/10.5753/etc.2018.3164

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.

Referências

Bellare, M. (1993). Interactive proofs and approximation: reductions from two provers in one round. In Theory and Computing Systems, 1993., Proceedings of the 2nd Israel Symposium on the, pages 266–274. IEEE.

Blanco, R., Boldi, P., and Marino, A. (2014). Entity-linking via graph-distance minimization. ArXiv e-prints.

Gouveia, L. and Martins, P. (2015). Solving the maximum edge-weight clique problem in sparse graphs with compact formulations. EURO Journal on Computational Optimization, 3(1):1–30.

Park, K., Lee, K., and Park, S. (1996). An extended formulation approach to the edge-weighted maximal clique problem. European Journal of Operational Research, 95(3):671–682.

Resende, M. G. (2011). Introdução aos algoritmos genéticos de chaves aleatórias viciadas. Simpósio Brasileiro de Pesquisa Operacional, pages 3680–3691.

Toso, R. and Resende, M. (2015). A c++application programming interface for biased random-key genetic algorithms. Optimization Methods and Software, 30(1):81–93.