| Texto completo | |
| Autor(es): |
Melo, Rafael A.
;
Ribeiro, Celso C.
;
Riveaux, Jose A.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ANNALS OF OPERATIONS RESEARCH; v. N/A, p. 33-pg., 2023-09-28. |
| Resumo | |
Let G=(V,E)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V, E)$$\end{document} be a graph with vertex set V and edge set E, and consider gamma is an element of[0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma \in [0,1)$$\end{document} to be a real constant. A gamma\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}-clique (or quasi-clique) is a subset V 'subset of V\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V'\subseteq V$$\end{document} inducing a subgraph of G with edge density at least gamma\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\gamma $$\end{document}. In this paper, we tackle the minimum quasi-clique partitioning problem (MQCPP), which consists of obtaining a minimum-cardinality partition of V into quasi-cliques. We propose a biased random-key genetic algorithm (BRKGA) relying on an efficient partitioning decoder that allows merge operations to combine smaller quasi-cliques into larger ones. Furthermore, we show that MQCPP and the problem of covering the graph with a minimum number of quasi-cliques are not equivalent. Computational experiments indicate that the proposed BRKGA is very effective in obtaining high-quality solutions for MQCPP in low computational times. More specifically, it can at least match all the best solutions available in the literature, strictly improving over them for 20.3% of the benchmark instances. Besides, the approach is robust as it obtains small deviations from the best-achieved solutions when executing multiple independent runs. We also consider the performance of our BRKGA on a new set of challenging large instances with up to 2851 vertices. (AU) | |
| Processo FAPESP: | 22/06747-0 - Métodos heurísticos aplicados ao problema multiobjetivo de programação de atividades de técnicos de campo |
| Beneficiário: | José Angel Riveaux Merino |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |