{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T13:50:37Z","timestamp":1718632237124},"reference-count":32,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2013,8]]},"abstract":" Tabu search (TS) has always been a very popular algorithm for graph coloring, both as a stand-alone optimizer as well as a subroutine inside population-based hybrid methods. We present two TS extensions that could allow previous TS algorithms to improve their behavior at almost no additional computational cost. First, we integrate two new evaluation functions which employ supplementary (structural or dynamic) information in addition to the conventional objective function (the number of edges with both ends of the same color). These new evaluation functions allow the search process to differentiate configurations not distinguished by the conventional evaluation function. The second extension concerns a reactive mechanism for improving the tabu list management. Theoretical arguments show that this reactive component completely eliminates the risk of getting blocked looping on plateaus. Numerical experiments show that the two proposed TS extensions can be very useful inside a stand-alone TS optimizer, as well as inside TS subroutines of state-of-the-art hybrid methods. <\/jats:p>","DOI":"10.1142\/s0217595913500103","type":"journal-article","created":{"date-parts":[[2013,6,26]],"date-time":"2013-06-26T11:32:58Z","timestamp":1372246378000},"page":"1350010","source":"Crossref","is-referenced-by-count":4,"title":["INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING"],"prefix":"10.1142","volume":"30","author":[{"given":"DANIEL COSMIN","family":"PORUMBEL","sequence":"first","affiliation":[{"name":"Univ. Lille-Nord de France, UArtois, LGI2A, Technoparc Futura, 62400 B\u00e9thune, France"}]},{"given":"JIN-KAO","family":"HAO","sequence":"additional","affiliation":[{"name":"Universit\u00e9 d'Angers, LERIA, 2 Bd Lavoisier, 49045 Angers, France"}]},{"given":"PASCALE","family":"KUNTZ","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Nantes, LINA, rue Christian Pauc, 44306 Nantes, France"}]}],"member":"219","published-online":{"date-parts":[[2013,8,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00832-9"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.2.126"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.05.014"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.07.012"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(87)80148-0"},{"key":"rf6","unstructured":"M.\u00a0Chiarandini, I.\u00a0Dumitrescu and T.\u00a0St\u00fctzle, Handbook of Approximation Algorithms and Metaheuristics, ed. T. F.\u00a0Gonzalez (Chapman & Hall, Boca Raton, FL, USA, 2007)\u00a0pp. 63.1\u201363.17."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600357"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.025"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(93)90279-5"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125407"},{"key":"rf14","unstructured":"C.\u00a0Fleurent and J. A.\u00a0Ferland, Cliques, Coloring, and Satisfiability Second DIMACS Implementation Challenge (1996)\u00a0pp. 619\u2013652."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009823419804"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2005.07.028"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.07.017"},{"key":"rf18","unstructured":"F.\u00a0Glover, M.\u00a0Parker and J.\u00a0Ryan, Cliques, Coloring, and Satisfiability Second DIMACS Implementation Challenge (1996)\u00a0pp. 285\u2013307."},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.03.022"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239976"},{"key":"rf21","volume-title":"Stochastic Local Search Foundations & Applications","author":"Hoos H.","year":"2004"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(96)00043-4"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.3.378"},{"key":"rf24","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1090\/dimacs\/026\/01","volume-title":"Cliques, Coloring, and Satisfiability Second DIMACS Implementation Challenge","volume":"26","author":"Johnson D. S.","year":"1996"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.07.016"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1070.0245"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1111\/j.1475-3995.2009.00696.x"},{"key":"rf29","unstructured":"C.\u00a0Morgenstern, Cliques, Coloring, and Satisfiability Second DIMACS Implementation Challenge (1996)\u00a0pp. 335\u2013358."},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1057\/jors.2009.27"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.01.015"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.06.024"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014496509129"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.08.034"},{"key":"rf38","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2011.04.002"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595913500103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:14:48Z","timestamp":1565183688000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595913500103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":32,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2013,8,6]]},"published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1142\/S0217595913500103"],"URL":"https:\/\/doi.org\/10.1142\/s0217595913500103","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"value":"0217-5959","type":"print"},{"value":"1793-7019","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}