Abstract
In this work, we propose a hybridization of GRASP metaheuristic that incorporates a data mining process. We believe that patterns obtained from a set of sub-optimal solutions, by using data mining techniques, can be used to guide the search for better solutions in metaheuristics procedures. In this hybrid GRASP proposal, after executing a significant number of GRASP iterations, the data mining process extracts patterns from an elite set of solutions which will guide the following iterations. To validate this proposal we have worked on the Set Packing Problem as a case study. Computational experiments, comparing traditional GRASP and different hybrid approaches, show that employing frequent patterns mined from an elite set of solutions conducted to better results. Besides, additional performed experiments evidence that data mining strategies accelerate the process of finding good solutions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agrawal, R., Imielinski, T. and Srikant, R.: Mining association rules between sets of items in large databases, in ACM SIGMOD Intl. Conf. on Management of Data, 1993, pp. 207–216.
Agrawal, R. and Srikant, R.: Fast algorithms for mining association rules, in 20th Very Large DataBase Conference, 1994, pp. 487–499.
Bastide, Y., Taouil, R., Pasquier, N., Stumme, G. and Lakhal, L.: Mining frequent patterns with counting inference, ACM SIGKDD Explorations Newsletter 2 (2000), 66–75.
Berry, M. L. A. and Linoff, G.: Data Mining Techniques: for Marketing, Sales and Customer Support, Wiley Computer, 1997.
Delorme, X., Gandibleux, X. and Rodriguez, J.: GRASP for set packing problems, Eur. J. Oper. Res. 153 (2003), 564–580.
Feo, T. A. and Resende, M. G. C.: Greedy randomized adaptive search procedures, J. Glob. Optim. 6 (1995), 109–133.
Gandibleux, X., Delorme, X. and T’Kindt, V.: An ant colony algorithm for the set packing problem, Note de Recherche, no 13, LAMIH-ROI, Université de Valeciennes et du Hainaut-Cambrésis, 2004.
Garey, M. R. and Johnson, D. S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, V. H. Freeman and Company, 1979.
Guo, Y., Lim, A., Rodrigues, B. and Zhu, Y.: Heuristics for a brokering set packing problem, in 8th Intl. Symposium on Artificial Intelligence and Mathematics, 2004.
Goethals, B. and Zaki, M. J.: Advances in frequent itemset mining implementations: introduction to FIMI’03, in IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
Grahne, G. and Zhu, J.: Efficiently using prefix-trees in mining frequent itemsets, in IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
Han, J. and Kamber, M.: Data Mining: Concepts and Techniques, Morgan Kaufmann, 2000.
Han, J., Pei, J. and Yin, Y.: Mining frequent patterns without candidate generation, in ACM SIGMOD Intl. Conf. on Management of Data, 2000, pp. 1–12.
Lodi, A., Allemand, K. and Liebling, T. M.: An evolutionary heuristic for quadratic 0-1 programming, Eur. J. Oper. Res. 119 (1999), 662–670.
Mingozzi, A., Maniezzo, V., Ricciardelli, S. and Bianco, L.: An exact algorithm for the project scheduling with resource constraints based on a new mathematical formulation, Manag. Sci. 44 (1998), 714–729.
Orlando, S., Palmerimi, P. and Perego, R.: Adaptive and resource-aware mining of frequent sets, in IEEE Intl. Conf. on Data Mining, 2002, pp. 338–345.
Orlando, S., Palmerimi, P., Perego, R., Lucchese, C. and Silvestri, F.: kDCI++: A multi–strategy algorithm for discovering frequent sets in large databases, in IEEE ICDM Workshop on Frequent Itemset Mining Implementations, 2003.
Padberg, M. W.: On the facial structure of set packing polyhedra, Math. Program. 5 (1973), 199–215.
Pardalos, P. M. and Rodgers, G. P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing 45 (1990), 131–144.
Park, J. S., Chen, M. and Yu, P. S.: An effective hash-based algorithm for mining association rules, in ACM SIGMOD Intl. Conf. on Management of Data, 1995, pp. 175–186.
Savasere, A., Omiecinski, E. and Navathe, S.: An efficient algorithm for mining association rules in large databases, in 21st Very Large DataBase Conference, 1995, pp. 432–444.
Talbi, E. G.: A taxonomy of hybrid metaheuristics, Journal of Heuristics 8 (2002), 541–564.
Zwaneveld, P. J., Kroon, L. G., Romeijin, H. E., Salomon, M., Dauzères-Pérès, S., Van Hoesel, S. P. and Ambergen, H. W.: Routing trains through railway stations: model formulation and algorithms, Trans. Sci. 30 (1996), 181–194.
Author information
Authors and Affiliations
Corresponding author
Additional information
★★Work sponsored by CNPq research grants 300879/00-8 and 475124/03-0.
†Work sponsored by CNPq research grant 475124/03-0.
Rights and permissions
About this article
Cite this article
Ribeiro, M.H., Plastino, A. & Martins, S.L. Hybridization of GRASP Metaheuristic with Data Mining Techniques. J Math Model Algor 5, 23–41 (2006). https://doi.org/10.1007/s10852-005-9030-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-005-9030-1