Given a graph G = (V, E) and a threshold γ ∈ (0, 1], the maximum cardinality quasi- clique problem consists in finding a maximum cardinality subset C* of the vertices in V such that the density of the graph induced in G by C* is greater than or equal to the threshold γ. This problem has a number of applications in data mining, e.g., in social networks or phone call graphs. We propose a matheuristic for solving the maximum cardinality quasi-clique problem, based on the hybridization of a biased random-key genetic algorithm (BRKGA) with an exact local search strategy. The newly proposed approach is compared with a pure biased random-key genetic algorithm, which was the best heuristic in the literature at the time of writing. Computational results show that the hybrid BRKGA outperforms the pure BRKGA.
Keywords: Maximum quasi-clique problem, maximum clique problem, biased random-key genetic algorithm, metaheuristics, matheuristics
@article{RO_2021__55_S1_S741_0,
author = {Pinto, Bruno Q. and Ribeiro, Celso C. and Riveaux, Jos\'e A. and Rosseti, Isabel},
title = {A {BRKGA-based} matheuristic for the maximum quasi-clique problem with an exact local search strategy},
journal = {RAIRO. Operations Research},
pages = {S741--S763},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020003},
mrnumber = {4223116},
zbl = {1469.05135},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020003/}
}
TY - JOUR AU - Pinto, Bruno Q. AU - Ribeiro, Celso C. AU - Riveaux, José A. AU - Rosseti, Isabel TI - A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy JO - RAIRO. Operations Research PY - 2021 SP - S741 EP - S763 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020003/ DO - 10.1051/ro/2020003 LA - en ID - RO_2021__55_S1_S741_0 ER -
%0 Journal Article %A Pinto, Bruno Q. %A Ribeiro, Celso C. %A Riveaux, José A. %A Rosseti, Isabel %T A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy %J RAIRO. Operations Research %D 2021 %P S741-S763 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020003/ %R 10.1051/ro/2020003 %G en %F RO_2021__55_S1_S741_0
Pinto, Bruno Q.; Ribeiro, Celso C.; Riveaux, José A.; Rosseti, Isabel. A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy. RAIRO. Operations Research, Tome 55 (2021), pp. S741-S763. doi: 10.1051/ro/2020003
, and , Massive quasi-clique detection, edited by J. Abello and J. Vitter. In: Proceedings of the 5th Latin American Symposium on the Theory of Informatics. Springer-Verlag Berlin Heidelberg (2002) 598–612. | MR | Zbl
, and , Probability distribution of solution time in GRASP: an experimental investigation. J. Heuristics 8 (2002) 343–373. | Zbl | DOI
, and , TTT PLOTS: a Perl program to create time-to-target plots. Optim. Lett. 1 (2007) 355–366. | MR | Zbl | DOI
, Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 2 (1994) 154–160. | Zbl | DOI
BHOSLIB, Benchmarks with hidden optimum solutions for graph problems. http://networkrepository.com/ (2004). Online reference, last visited on June 7, 2018.
, , and , A biased random-key genetic algorithm for single-round divisible load scheduling. Int. Trans. Oper. Res. 22 (2015) 823–839. | MR | Zbl | DOI
, , and , A biased random-key genetic algorithm for scheduling heterogeneous multi-round systems. Int. Trans. Oper. Res. 27 (2017) 1061–1077. | MR | Zbl | DOI
, and , On effectively finding maximal quasi-cliques in graphs, Learning and Intelligent Optimization edited by , and . In: Vol. 5313 of Lecture Notes in Computer Science. Springer, Berlin (2008) 41–55. | DOI
and , The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38 (2011) 1–25. | MR | Zbl | DOI
FICO, FICO Xpress Optimization Suite 7.6. http://www.fico.com/en/products/fico-xpress-optimization-suite (2017).
and , Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17 (2011) 487–525. | DOI
, and , Biased and unbiased random key genetic algorithms: an experimental analysis. In: Abstracts of the 10th Metaheuristics International Conference. Singapore (2013).
and , Evaluation of Las Vegas algorithms – Pitfalls and remedies, edited by and . In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Madison (1998) 238–245.
, Cliques, coloring, and satisfiability: second DIMACS implementation challenge. In: Vol. 26 of Dimacs Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, Providence (1996). | Zbl | DOI
, Reducibility among combinatorial problems. In: Complexity of Computer Computations, edited by and . Plenum, New York (1972) 85–103. | MR | Zbl | DOI
, , and , The IRACE package: Iterated race for automatic algorithm configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium (2011).
, and , A biased random-key genetic algorithm for routing and wavelength assignment. J. Global Optim. 50 (2011) 503–518. | DOI
, and , Construction heuristics for the maximum cardinality quasi-clique problem. In: Abstracts of the 10th Metaheuristics International Conference. Singapore (2013) 84.
, and , A branch-and-bound approach for maximum quasi-cliques. Ann. Oper. Res. 216 (2014) 145–161. | MR | Zbl | DOI
, , and , On maximum degree-based -quasi-clique problem: complexity and exact approaches. Networks 71 (2018) 136–152. | MR | Zbl | DOI
, , and , On the maximum quasi-clique problem. Discrete Appl. Math. 161 (2013) 244–257. | MR | Zbl | DOI
, and , An analysis of parameters of IRACE. In: Proceedings of the 14th European Conference on Evolutionary Computation in Combinatorial Optimization. Vol. 8600 of Lecture Notes in Computer Science. Springer, Berlin (2014) 37–48.
, , and , A biased random-key genetic algorithm for solving the maximum quasi- clique problem. Eur. J. Oper. Res. 271 (2018) 849–865. | MR | Zbl | DOI
and , Biased-random key genetic algorithms: an advanced tutorial. In: Proceedings of the 2016 Genetic and Evolutionary Computation Conference – GECCO’16 Companion Volume. Association for Computing Machinery, Denver (2016) 483–514.
and , An exact algorithm for the maximum quasi-clique problem. Int. Trans. Oper. Res. 26 (2019) 2199–2229. | MR | Zbl | DOI
and , Coloring large complex networks. Soc. Network Anal. Min. 4 (2014) 1–37.
and , The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015) 4292–4293.
, An improved algorithm for exact graph coloring, Cliques, Coloring, and Satisfiability, edited by and . In: Vol. 26 of 2nd DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society (1996) 359–373. | Zbl | DOI
and , On the virtues of parameterized uniform crossover, edited by and . Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufman, San Mateo (1991) 230–236.
and , A C++ application programming interface for biased random-key genetic algorithms. Optim. Methods Softw. 30 (2015) 81–93. | DOI
, , , and , Exact MIP-based approaches for finding maximum quasi-clique and dense subgraph. Comput. Optim. App. 64 (2016) 177–214. | MR | Zbl | DOI
Cité par Sources :
