GRASP Metaheuristic Executions

Introduction This dataset contains the cost values obtained at executions of the metaheuristic Greedy Randomized Adaptive Search Procedures (GRASP). An execution is the act of running the metaheuristic to solve an instance of an optimization problem, using some seed (for the random number generator). In the context of this dataset, that term is also used to denote the sequence of costs obtained at each iteration during an execution. The problems covered are the Quadratic Assignment Problem (QAP), the Uncapacitated p-Median Problem (PMP) and the Set k-Covering Problem (SCP). In the case of the SCP, the instances were run with k=2. The total number of instances is 184 and, for each instance, 10, 20 or 30 different executions (with different seeds) were generated. The specific number of executions per instance, as well as execution length and some other basic statistics and information can be checked in the file raw_exec_stats.csv or be easily calculated from the data it provides. The QAP instances come from the QAPLIB [1] and the executions were produced by the GRASP implementation of [2]. Meanwhile, SCP instances are from the OR-Library [3] and were run by the GRASP of [4]. As for the PMP, the instances are also from the OR-Library, but a naive implementation of the metaheuristic [5] was used to run them. In all implementations, the metaheuristic was run in its standard form, which means that techniques like Path-Relinking and Reactive GRASP were not used (they were disabled if available). The information up to this point is summarized by the following table, including the number of instances available for each problem. Problem Number of Instances Instance Source GRASP Implementation QAP 132 QAPLIB [2] PMP 7 OR-Library [5] SCP (k=2) 45 OR-Library [4] Dataset Structure Regarding the structure of the dataset, there are five files, that are described as follows. raw_exec_stats.csv Contains a list of execution statistics and other relevant information. Each row contains the following fields: instance: instance name. seed: the seed used by the random number generator during the execution. problem: the optimization problem the instance belongs to. num_costs: number of costs and, consequently, the number of iterations in the execution. unique_costs: number of unique cost values in the execution. costs_min: minimum cost in the execution. costs_max: maximum cost in the execution. costs_mean: mean of the cost values in the execution. costs_std: sample standard deviation of the cost values in the execution. costs_skewness: skewness of the cost value distribution. costs_kurtosis: excess kurtosis of the cost value distribution. know_lb: cost of the best known solution from the literature for the given instance. reached_known_lb: boolean indicating if the best known solution was reached in the execution. file_name: name of the CSV file containing the execution. zip_name: name of the ZIP file containing the CSV file that contains the execution. This file was saved in UTF-7. boundaries.csv Contains lower bounds for the instances available in the dataset. They come from a series of works. In the case of the QAP they were obtained from the QAPLIB, that also lists the proper sources on its website. As for the other problems, the lower bounds for the SCP instances come from [4], and the ones for the PMP are available on OR-Library's website. For the three problems, if upper bounds are needed, they can be calculated through the methods described in [7]. Each row of the file contains the following fields: instance: instance name. lb: the cost of the best known solution for that instance in the literature. pmp_executions.zip Compressed file containing the CSVs of each execution belonging to the PMP instances (those files are also compressed individually). The files are named using the pattern {instance}_{seed}_raw.{csv|zip}, where instance and seed are as described in the case of the file raw_exec_stats.csv. For a given execution, its CSV contains only one column, called costs, and the cost in the first row belongs to the first iteration, the cost in the second row belongs to the second, and so on. qap_executions.zip Same as in the case of the file pmp_executions.zip, but the instances belong to the QAP problem. scp_executions.zip Same as in the case of the file pmp_executions.zip, but the instances belong to the SCP problem. Related Work The version 1 of this dataset is associated with a paper called "Ensemble machine learning-based stopping rule for greedy randomized adaptive search procedure", which is identified by the DOI 10.1051/ro/2026007. Suggested citation (APA): de Mattos, G. C., Lusquino Filho, L. A. D., Simonetti, L. G., & Lima, P. M. V. (2026). Ensemble machine learning-based stopping rule for greedy randomized adaptive search procedure. RAIRO - Operations Research, 60(2), 643–684. https://doi.org/10.1051/ro/2026007 That paper was originally titled "Ensemble-based stopping rule for GRASP", but it changed during the review process. Acknowledgements The authors thank the Núcleo Avançado de Computação de Alto Desempenho (NACAD) of the Federal University of Rio de Janeiro and Professor Felipe M. G. França for their collaboration with an earlier, different version of this dataset that was used in [8]. Funding The data collection was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code 001. References [1] Burkard, R. E., Karisch, S. E., & Rendl, F. (1997). Journal of Global Optimization, 10(4), 391–403. https://doi.org/10.1023/a:1008293323270 [2] Oliveira, C. A. S., Pardalos, P. M., & Resende, M. G. C. (2004). GRASP with Path-Relinking for the Quadratic Assignment Problem. In Lecture Notes in Computer Science (pp. 356–368). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-24838-5_27 [3] Beasley, J. E. (1990). OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society, 41(11), 1069–1072. https://doi.org/10.1057/jors.1990.166 [4] Pessoa, L. S., Resende, M. G. C., & Ribeiro, C. C. (2013). A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering. Computers & Operations Research, 40(12), 3132–3146. https://doi.org/10.1016/j.cor.2011.11.018 [5] Mattos, G.C. (2023) GRASP p-Median C++: Naive C++ implementation of the GRASP metaheuristic for the p-Median problem, GitHub. Available at: https://github.com/GuilhermeCaeiro/grasp_pmedian_cpp (Accessed: 27 May 2025). [6] Beasley, J. E. (1985). A note on solving large p-median problems. European Journal of Operational Research, 21(2), 270–273. https://doi.org/10.1016/0377-2217(85)90040-2 [7] Ribeiro, C. C., Rosseti, I., & Souza, R. C. (2013). Probabilistic stopping rules for GRASP heuristics and extensions. International Transactions in Operational Research, 20(3), 301–323. https://doi.org/10.1111/itor.12010 [8] Mattos, G. C. (2021). Machine Learning-Based Probabilistic Stopping Rule for The GRASP Metaheuristic [Master's dissertation, Federal University of Rio de Janeiro]. https://www.cos.ufrj.br/index.php/pt-BR/publicacoes-pesquisa/details/15/3022