Carousel greedy: a generalized greedy algorithm with applications in optimization. (English) Zbl 1458.90643
Summary: In this paper, we introduce carousel greedy, an enhanced greedy algorithm which seeks to overcome the traditional weaknesses of greedy approaches. We have applied carousel greedy to a variety of well-known problems in combinatorial optimization such as the minimum label spanning tree problem, the minimum vertex cover problem, the maximum independent set problem, and the minimum weight vertex cover problem. In all cases, the results are very promising. Since carousel greedy is very fast, it can be used to solve very large problems. In addition, it can be combined with other approaches to create a powerful, new metaheuristic. Our goal in this paper is to motivate and explain the new approach and present extensive computational results.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
Keywords:
metaheuristics; greedy algorithm; combinatorial optimization; minimum label spanning tree; vertex cover; independent set; iterated greedy; carousel greedyReferences:
| [1] | Battiti, R.; Brunato, M., The LION way. machine learning plus intelligent optimization, (April 2015), Version 2.0 |
| [2] | Blum, C.; Roli, A., Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM Comput Surv, 35, 3, 268-308, (2003) |
| [3] | Bouamama, S.; Blum, C.; Boukerram, A., A population-based iterated greedy algorithm for the minimum weight vertex cover problem, Appl Soft Comput, 12, 6, 1632-1639, (2012) |
| [4] | Captivo, M. E.; Clímaco, J. C.; Pascoal, M. M., A mixed integer linear formulation for the minimum label spanning tree problem, Comput Oper Res, 36, 11, 3082-3085, (2009) · Zbl 1162.90575 |
| [5] | Carrabs, F.; Cerrone, C.; Cerulli, R., A memetic algorithm for the weighted feedback vertex set problem, Networks, 64, 4, 339-356, (2014) |
| [6] | Cerrone, C.; Cerulli, R.; Gaudioso, M., Omega one multi ethnic genetic approach, Optimization Letters, 10, 2, 309-324, (2016) · Zbl 1343.90105 |
| [7] | Cerulli, R.; Fink, A.; Gentili, M.; Voß, S., Metaheuristics comparison for the minimum labelling spanning tree problem, The Next Wave in Computing, Optimization, and Decision Technologies (B. Golden, S. Raghavan, and E.Wasil, eds.), 93-106, (2005), Springer |
| [8] | Chang, R.-S.; Shing-Jiuan, L., The minimum labeling spanning trees, Inf Process Lett, 63, 5, 277-282, (1997) · Zbl 0938.90063 |
| [9] | Chvatal, V., A greedy heuristic for the set-covering problem, Mathematics of Operations Research, 4, 3, 233-235, (1979) · Zbl 0443.90066 |
| [10] | Clarkson, K. L., A modification of the greedy algorithm for vertex cover, Inf Process Lett, 16, 1, 23-25, (1983) |
| [11] | Consoli, S.; Darby-Dowman, K.; Mladenović, N.; Moreno Pérez, J. A., Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem, Eur J Oper Res, 196, 2, 440-449, (2009) · Zbl 1163.90766 |
| [12] | Consoli, S.; Mladenović, N.; Pérez, J. M., Solving the minimum labelling spanning tree problem by intelligent optimization, Appl Soft Comput, 28, 440-452, (2015) |
| [13] | Consoli, S.; Pérez, J. M., Solving the minimum labelling spanning tree problem using hybrid local search, Electronic Notes in Discrete Mathematics, 39, 75-82, (2012) · Zbl 1268.90137 |
| [14] | Draper, N. R.; Smith, H., Applied regression analysis 2nd ed., New York New York John Wiley and Sons, (1981) · Zbl 0548.62046 |
| [15] | Duin, C.; Voß, S., The pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs, Networks, 34, 3, 181-191, (1999) · Zbl 0980.90094 |
| [16] | Feo, T. A.; Resende, M. G., A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8, 2, 67-71, (1989) · Zbl 0675.90073 |
| [17] | Feo, T. A.; Resende, M. G., Greedy randomized adaptive search procedures, J. Global Optim., 6, 2, 109-133, (1995) · Zbl 0822.90110 |
| [18] | Friedman, M., The use of ranks to avoid the assumption of normality implicit in the analysis of variance, J Am Stat Assoc, 32, 200, 675-701, (1937) · JFM 63.1098.02 |
| [19] | Glover, F., Multi-start and strategic oscillation methods-principles to exploit adaptive memory, Computing Tools for Modeling, Optimization and Simulation (M. Laguna and J.L. González-Velarde, eds.), 1-23, (2000), Kluwer |
| [20] | Glover, F.; Alidaee, B.; Rego, C.; Kochenberger, G., One-pass heuristics for large-scale unconstrained binary quadratic problems, Eur J Oper Res, 137, 2, 272-287, (2002) · Zbl 1030.90074 |
| [21] | Harary, F., Graph theory, (1972), Addison Wesley Publishing Company. Reading, MA, USA · Zbl 0797.05064 |
| [22] | Hirst, J. D.; King, R. D.; Sternberg, M. J., Quantitative structure-activity relationships by neural networks and inductive logic programming. i. the inhibition of dihydrofolate reductase by pyrimidines, J. Comput. Aided Mol. Des., 8, 4, 405-420, (1994) |
| [23] | Hochbaum, D. S., Efficient bounds for the stable set, vertex cover and set packing problems, Discrete Appl. Math., 6, 3, 243-254, (1983) · Zbl 0523.05055 |
| [24] | Hoffman, K. L.; Padberg, M.; Rinaldi, G., Traveling salesman problem, Encyclopedia of Operations Research and Management Science, 1573-1578, (2013), Springer |
| [25] | Johnson, D. S.; Trick, M. A., Cliques, coloring, and satisfiability: second DIMACS implementation challenge, October 11-13, 1993, 26, (1996), American Mathematical Soc · Zbl 0851.00080 |
| [26] | Jovanovic, R.; Tuba, M., An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem, Appl Soft Comput, 11, 8, 5360-5366, (2011) |
| [27] | Karp, R. M., Reducibility among combinatorial problems, Complexity of Computer Computations (R.E. Miller and J.W. Thatcher, eds.), 85-103, (1972), Plenum Press, New York · Zbl 1467.68065 |
| [28] | Ke, X.,. Bhoslib: Benchmarks with hidden optimum solutions for graph problems (maximum clique, maximum independent set, minimum vertex cover and vertex coloring) - hiding exact solutions in random graphs. http://www.nlsde.buaa.edu.cn/ kexu/benchmarks/graph-benchmarks.htm. |
| [29] | Krumke, S. O.; Wirth, H.-C., On the minimum label spanning tree problem, Inf Process Lett, 66, 2, 81-85, (1998) · Zbl 0938.90064 |
| [30] | Mangold, W. D.; Bean, L.; Adams, D., The impact of intercollegiate athletics on graduation rates among major NCAA division i universities: implications for college persistence theory and practice, J Higher Educ, 74, 5, 540-562, (2003) |
| [31] | Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur J Oper Res, 177, 3, 2033-2049, (2007) · Zbl 1110.90042 |
| [32] | Shyu, S. J.; Yin, P.-Y.; Lin, B. M., An ant colony optimization algorithm for the minimum weight vertex cover problem, Ann Oper Res, 131, 1-4, 283-304, (2004) · Zbl 1066.90135 |
| [33] | Voß, S.; Fink, A., A hybridized tabu search approach for the minimum weight vertex cover problem, Journal of Heuristics, 18, 6, 869-876, (2012) |
| [34] | Voßs, S.; Fink, A.; Duin, C., Looking ahead with the pilot method, Ann Oper Res, 136, 1, 285-302, (2005) · Zbl 1114.90064 |
| [35] | Xiong, Y.; Golden, B.; Wasil, E., A one-parameter genetic algorithm for the minimum labeling spanning tree problem, IEEE Trans. Evol. Comput., 9, 1, 55-60, (2005) |
| [36] | Xiong, Y.; Golden, B.; Wasil, E., Improved heuristics for the minimum label spanning tree problem, IEEE Trans. Evol. Comput., 10, 6, 700-703, (2006) |
| [37] | Zhou, T.; Lü, Z.; Wang, Y.; Ding, J.; Peng, B., Multi-start iterated tabu search for the minimum weight vertex cover problem, Journal of Combinatorial Optimization, 32, 2, 368-384, (2016) · Zbl 1353.90136 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
