{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T16:18:33Z","timestamp":1761581913741,"version":"3.37.3"},"reference-count":31,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"vor","delay-in-days":60,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico - CNPq","award":["303958\/2015-4","425778\/2016-9","310624\/2018-5"],"award-info":[{"award-number":["303958\/2015-4","425778\/2016-9","310624\/2018-5"]}]},{"name":"Funda\u00e7\u00e3o Carlos Chagas Filho de Amparo \u00e0 Pesquisa do Estado do Rio de Janeiro \u0096 FAPERJ","award":["E-26\/202.854\/2017"],"award-info":[{"award-number":["E-26\/202.854\/2017"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2020,1,4]]},"published-print":{"date-parts":[[2021]]},"abstract":"<jats:p>Given a graph <jats:italic>G<\/jats:italic> = (<jats:italic>V, E<\/jats:italic>) and a threshold \u03b3 \u2208 (0, 1], the maximum cardinality quasi- clique problem consists in finding a maximum cardinality subset <jats:italic>C<\/jats:italic>* of the vertices in <jats:italic>V<\/jats:italic> such that the density of the graph induced in <jats:italic>G<\/jats:italic> by <jats:italic>C<\/jats:italic>* is greater than or equal to the threshold \u03b3. This problem has a number of applications in data mining, <jats:italic>e.g<\/jats:italic>., 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.<\/jats:p>","DOI":"10.1051\/ro\/2020003","type":"journal-article","created":{"date-parts":[[2020,1,7]],"date-time":"2020-01-07T08:59:50Z","timestamp":1578387590000},"page":"S741-S763","source":"Crossref","is-referenced-by-count":14,"special_numbering":"Supplement","title":["A BRKGA-based matheuristic for the maximum quasi-clique problem with an exact local search strategy"],"prefix":"10.1051","volume":"55","author":[{"given":"Bruno Q.","family":"Pinto","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9478-2351","authenticated-orcid":false,"given":"Celso C.","family":"Ribeiro","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9 A.","family":"Riveaux","sequence":"additional","affiliation":[]},{"given":"Isabel","family":"Rosseti","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"key":"R1","unstructured":"Abello J., Resende M. and Sudarsky S., 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\u2013612."},{"key":"R2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1023\/A:1015061802659","volume":"8","author":"Aiex","year":"2002","journal-title":"J. Heuristics"},{"key":"R3","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s11590-006-0031-4","volume":"1","author":"Aiex","year":"2007","journal-title":"Optim. Lett"},{"key":"R4","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1287\/ijoc.6.2.154","volume":"2","author":"Bean","year":"1994","journal-title":"ORSA J. Comput"},{"key":"R5","unstructured":"BHOSLIB, Benchmarks with hidden optimum solutions for graph problems. http:\/\/networkrepository.com\/ (2004). Online reference, last visited on June 7, 2018."},{"key":"R6","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1111\/itor.12178","volume":"22","author":"Brand\u00e3o","year":"2015","journal-title":"Int. Trans. Oper. Res"},{"key":"R7","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1111\/itor.12429","volume":"27","author":"Brand\u00e3o","year":"2017","journal-title":"Int. Trans. Oper. Res"},{"key":"R8","unstructured":"Brunato M., Hoos H. and Battiti R., On effectively finding maximal quasi-cliques in graphs, Learning and Intelligent Optimization edited by Maniezzo V., Battiti R. and Watson J.-P.. In: Vol. 5313 of Lecture Notes in Computer Science. Springer, Berlin (2008) 41\u201355."},{"key":"R9","first-page":"1","volume":"38","author":"Davis","year":"2011","journal-title":"ACM Trans. Math. Softw"},{"key":"R10","unstructured":"FICO, FICO Xpress Optimization Suite 7.6. http:\/\/www.fico.com\/en\/products\/fico-xpress-optimization-suite (2017)."},{"key":"R11","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s10732-010-9143-1","volume":"17","author":"Gon\u00e7alves","year":"2011","journal-title":"J. Heuristics"},{"key":"R12","unstructured":"Gon\u00e7alves J.F., Resende M.G.C. and Toso R.F., Biased and unbiased random key genetic algorithms: an experimental analysis. In: Abstracts of the 10th Metaheuristics International Conference. Singapore (2013)."},{"key":"R13","unstructured":"Hoos H. and St\u00fctzle T., Evaluation of Las Vegas algorithms \u2013 Pitfalls and remedies, edited by Cooper G. and Moral S.. In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Madison (1998) 238\u2013245."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Johnson D.S., 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).","DOI":"10.1090\/dimacs\/026"},{"key":"R15","unstructured":"Karp R.M., Reducibility among combinatorial problems. In: Complexity of Computer Computations, edited by Miller R.E. and Thatcher J.W.. Plenum, New York (1972) 85\u2013103."},{"key":"R16","unstructured":"L\u00f3pez-Ib\u00e1nez M., Dubois-Lacoste J., St\u00fctzle T. and Birattari M., The IRACE package: Iterated race for automatic algorithm configuration. Technical Report TR\/IRIDIA\/2011-004, IRIDIA, Universit\u00e9 Libre de Bruxelles, Belgium (2011)."},{"key":"R17","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/s10898-010-9608-7","volume":"50","author":"Noronha","year":"2011","journal-title":"J. Global Optim"},{"key":"R18","unstructured":"Oliveira A.B., Plastino A. and Ribeiro C.C., Construction heuristics for the maximum cardinality quasi-clique problem. In: Abstracts of the 10th Metaheuristics International Conference. Singapore (2013) 84."},{"key":"R19","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s10479-012-1242-y","volume":"216","author":"Pajouh","year":"2014","journal-title":"Ann. Oper. Res"},{"key":"R20","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1002\/net.21791","volume":"71","author":"Pastukhov","year":"2018","journal-title":"Networks"},{"key":"R21","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/j.dam.2012.07.019","volume":"161","author":"Pattillo","year":"2013","journal-title":"Discrete Appl. Math"},{"key":"R22","unstructured":"P\u00e9rez C\u00e1ceres L., L\u00f3pez-Ib\u00e1\u00f1ez M. and St\u00fctzle T., 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\u201348."},{"key":"R23","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1016\/j.ejor.2018.05.071","volume":"271","author":"Pinto","year":"2018","journal-title":"Eur. J. Oper. Res"},{"key":"R24","unstructured":"Resende M.G.C. and Ribeiro C.C., Biased-random key genetic algorithms: an advanced tutorial. In: Proceedings of the 2016 Genetic and Evolutionary Computation Conference \u2013 GECCO\u201916 Companion Volume. Association for Computing Machinery, Denver (2016) 483\u2013514."},{"key":"R25","doi-asserted-by":"crossref","first-page":"2199","DOI":"10.1111\/itor.12637","volume":"26","author":"Ribeiro","year":"2019","journal-title":"Int. Trans. Oper. Res"},{"key":"R26","first-page":"1","volume":"4","author":"Rossi","year":"2014","journal-title":"Soc. Network Anal. Min"},{"key":"R27","unstructured":"Rossi R.A. and Ahmed N.K., The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015) 4292\u20134293."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Sewell E.C., An improved algorithm for exact graph coloring, Cliques, Coloring, and Satisfiability, edited by Johnson D.S. and Trick M.A.. In: Vol. 26 of 2nd DIMACS Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society (1996) 359\u2013373.","DOI":"10.1090\/dimacs\/026\/17"},{"key":"R29","unstructured":"Spears W. and de Jong K., On the virtues of parameterized uniform crossover, edited by Belew R. and Booker L.. Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufman, San Mateo (1991) 230\u2013236."},{"key":"R30","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1080\/10556788.2014.890197","volume":"30","author":"Toso","year":"2015","journal-title":"Optim. Methods Softw"},{"key":"R31","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s10589-015-9804-y","volume":"64","author":"Veremyev","year":"2016","journal-title":"Comput. Optim. App"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020003\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,31]],"date-time":"2021-03-31T09:34:06Z","timestamp":1617183246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2020003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"references-count":31,"alternative-id":["ro190168"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2020003","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021]]}}}