| Full text | |
| Author(s): |
Melo, Rafael A.
;
Ribeiro, Celso C.
;
Riveaux, Jose A.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | ANNALS OF OPERATIONS RESEARCH; v. N/A, p. 33-pg., 2023-09-28. |
| Abstract | |
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) | |
| FAPESP's process: | 22/06747-0 - Multiobjective heuristic methods for the field technician scheduling problem |
| Grantee: | José Angel Riveaux Merino |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |