Construct, Merge, Solve & Adapt A new general algorithm for combinatorial optimization. (English) Zbl 1349.90705
Summary: This paper describes a general hybrid metaheuristic for combinatorial optimization labelled Construct, Merge, Solve & Adapt. The proposed algorithm is a specific instantiation of a framework known from the literature as Generate-And-Solve, which is based on the following general idea. First, generate a reduced sub-instance of the original problem instance, in a way such that a solution to the sub-instance is also a solution to the original problem instance. Second, apply an exact solver to the reduced sub-instance in order to obtain a (possibly) high quality solution to the original problem instance. And third, make use of the results of the exact solver as feedback for the next algorithm iteration. The minimum common string partition problem and the minimum covering arborescence problem are chosen as test cases in order to demonstrate the application of the proposed algorithm. The obtained results show that the algorithm is competitive with the exact solver for small to medium size problem instances, while it significantly outperforms the exact solver for larger problem instances.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 68T05 | Learning and adaptive systems in artificial intelligence |
Keywords:
metaheuristics; exact solver; hybrid algorithms; minimum common string partition; minimum covering arborescenceSoftware:
iraceReferences:
| [1] | Blum, C.; Puchinger, J.; Raidl, G.; Roli, A., Hybrid metaheuristics in combinatorial optimizationa survey, Appl Soft Comput, 11, 6, 4135-4151 (2011) |
| [2] | (Talbi, E.-G., Hybrid metaheuristics, Studies in computational intelligence, No. 434 (2013), Springer Verlag: Springer Verlag Berlin, Germany) |
| [3] | Raidl, G. R., Decomposition based hybrid metaheuristics, Eur J Oper Res, 244, 1, 66-76 (2015) · Zbl 1346.90827 |
| [5] | Wolsey, L. A., Integer programming (1998), Wiley-Interscience: Wiley-Interscience Hoboken, NJ · Zbl 0299.90012 |
| [10] | Pinheiro, P. R.; Coelho, A. L.V.; de Aguiar, A. B.; Bonates, T. O., On the concept of density control and its application to a hybrid optimization frameworkinvestigation into cutting problems, Comput Ind Eng, 61, 3, 463-472 (2011) |
| [11] | Saraiva, R. D.; Nepomuceno, N. V.; Pinheiro, P. R., The generate-and-solve framework revisitedgenerating by simulated annealing, (Middendorf, M.; Blum, C., Evolutionary computation in combinatorial optimization. Lecture notes in computer science, vol. 7832 (2013), Springer: Springer Berlin, Heidelberg), 262-273 |
| [12] | Coudert, D.; Nepomuceno, N. V.; Tahiri, I., Energy saving in fixed wireless broadband networks, (Pahl, J.; Reiners, T.; Voß, S., Proceedings of INOC 2011 - fifth international conference on network optimization. Lecture notes in computer science, vol. 6701 (2011), Springer: Springer Berlin, Heidelberg), 484-489 |
| [13] | Coudert, D.; Nepomuceno, N.; Rivano, H., Power-efficient radio configuration in fixed broadband wireless networks, Comput Commun, 33, 8, 898-906 (2010) |
| [16] | Cook, W.; Seymour, P., Tour merging via branch-decomposition, INFORMS J Comput, 15, 3, 233-248 (2003) · Zbl 1238.90128 |
| [20] | Blum, C.; Calvo, B., A matheuristic for the minimum weight rooted arborescence problem, J Heuristics, 21, 4, 479-499 (2015) |
| [22] | Mousavi, S.; Babaie, M.; Montazerian, M., An improved heuristic for the far from most strings problem, J Heuristics, 18, 239-262 (2012) |
| [23] | Meneses, C.; Oliveira, C.; Pardalos, P., Optimization techniques for string selection and comparison problems in genomics, IEEE Eng Med Biol Mag, 24, 3, 81-87 (2005) |
| [24] | Hsu, W. J.; Du, M. W., Computing a longest common subsequence for a set of strings, BIT Numer Math, 24, 1, 45-59 (1984) · Zbl 0528.68049 |
| [25] | Smith, T.; Waterman, M., Identification of common molecular subsequences, J Mol Biol, 147, 1, 195-197 (1981) |
| [26] | Gusfield, D., Algorithms on strings, trees, and sequences, computer science and computational biology (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0934.68103 |
| [27] | Garey, M. R.; Johnson, D. S., Computers and intractability; a guide to the theory of NP-completeness (1979), W. H. Freeman: W. H. Freeman San Francisco, LA · Zbl 0411.68039 |
| [29] | Kolman, P.; Waleń, T., Reversal distance for strings with duplicateslinear time approximation using hitting set, (Erlebach, T.; Kaklamanis, C., Proceedings of WAOA 2007 - fourth international workshop on approximation and online algorithms. Lecture notes in computer science, vol. 4368 (2007), Springer: Springer Berlin, Heidelberg), 279-289 · Zbl 1129.68431 |
| [30] | Goldstein, I.; Lewenstein, M., Quick greedy computation for minimum common string partitions, (Giancarlo, R.; Manzini, G., Proceedings of CPM 2011 - 22nd annual symposium on combinatorial pattern matching. Lecture notes in computer science, vol. 6661 (2011), Springer: Springer Berlin, Heidelberg), 273-284 · Zbl 1339.68332 |
| [31] | He, D., A novel greedy algorithm for the minimum common string partition problem, (Mandoiu, I.; Zelikovsky, A., Proceedings of ISBRA 2007 - third international symposium on bioinformatics research and applications. Lecture notes in computer science, vol. 4463 (2007), Springer: Springer Berlin, Heidelberg), 441-452 |
| [32] | Ferdous, S. M.; Sohel Rahman, M., Solving the minimum common string partition problem with the help of ants, (Tan, Y.; Shi, Y.; Mo, H., Proceedings of ICSI 2013 - fourth international conference on advances in swarm intelligence. Lecture notes in computer science, vol. 7928 (2013), Springer: Springer Berlin, Heidelberg), 306-313 |
| [34] | Blum, C.; Lozano, J. A.; Pinacho Davidson, P., Iterative probabilistic tree search for the minimum common string partition problem, (Blesa, M. J.; Blum, C.; Voss, S., Proceedings of HM 20104 - ninth international workshop on hybrid metaheuristics. Lecture notes in computer science, vol. 8457 (2014), Springer Verlag: Springer Verlag Berlin, Germany), 154 |
| [35] | Blum, C.; Lozano, J. A.; Pinacho Davidson, P., Mathematical programming strategies for solving the minimum common string partition problem, Eur J Oper Res, 242, 3, 769-777 (2015) · Zbl 1341.90107 |
| [37] | Tutte, W. T., Graph theory (2001), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 0964.05001 |
| [38] | Bang-Jensen, J.; Gutin, G. Z., Digraphs: theory, algorithms and applications (2008), Springer Science and Business Media: Springer Science and Business Media London, UK |
| [39] | Venkata Rao, V.; Sridharan, R., Minimum-weight rooted not-necessarily-spanning arborescence problem, Networks, 39, 2, 77-87 (2002) · Zbl 1001.90059 |
| [40] | Duhamel, C.; Gouveia, L.; Moura, P.; Souza, M., Models and heuristics for a minimum arborescence problem, Networks, 51, 1, 34-47 (2008) · Zbl 1175.90059 |
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.
