INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING

Daniel Cosmin Porumbel (), Jin-Kao Hao () and Pascale Kuntz ()
Additional contact information
Daniel Cosmin Porumbel: Univ. Lille-Nord de France, UArtois, LGI2A, Technoparc Futura, 62400 Béthune, France
Jin-Kao Hao: Université d'Angers, LERIA, 2 Bd Lavoisier, 49045 Angers, France
Pascale Kuntz: Université de Nantes, LINA, rue Christian Pauc, 44306 Nantes, France

Asia-Pacific Journal of Operational Research (APJOR), 2013, vol. 30, issue 04, 1-20

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.

Keywords: Discriminative evaluation function; tabu search; heuristics; graph coloring (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595913500103
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:30:y:2013:i:04:n:s0217595913500103

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595913500103

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().