A tabu search heuristic for the equitable coloring problem

The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algor...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Méndez Díaz, Isabel, Severin, Daniel E.
Publicado: 2014
Materias:
Combinatorial optimization
Equitable coloring
Tabu search
Benchmarking
Heuristic algorithms
Heuristic methods
Arbitrary color
Computational experiment
Exact algorithms
Graph coloring problem
Large-sized
Local search
Tabu Search heuristic
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p347_MendezDiaz
http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p347_MendezDiaz
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03029743_v8596LNCS_n_p347_MendezDiaz
record_format dspace
spelling paper:paper_03029743_v8596LNCS_n_p347_MendezDiaz2023-06-08T15:28:54Z A tabu search heuristic for the equitable coloring problem Méndez Díaz, Isabel Severin, Daniel E. Combinatorial optimization Equitable coloring Tabu search Benchmarking Combinatorial optimization Heuristic algorithms Heuristic methods Arbitrary color Computational experiment Equitable coloring Exact algorithms Graph coloring problem Large-sized Local search Tabu Search heuristic Tabu search The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given. Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances. © 2014 Springer International Publishing. Fil:Méndez Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Severín, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p347_MendezDiaz http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p347_MendezDiaz
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Combinatorial optimization
Equitable coloring
Tabu search
Benchmarking
Combinatorial optimization
Heuristic algorithms
Heuristic methods
Arbitrary color
Computational experiment
Equitable coloring
Exact algorithms
Graph coloring problem
Large-sized
Local search
Tabu Search heuristic
Tabu search
spellingShingle Combinatorial optimization
Equitable coloring
Tabu search
Benchmarking
Combinatorial optimization
Heuristic algorithms
Heuristic methods
Arbitrary color
Computational experiment
Equitable coloring
Exact algorithms
Graph coloring problem
Large-sized
Local search
Tabu Search heuristic
Tabu search
Méndez Díaz, Isabel
Severin, Daniel E.
A tabu search heuristic for the equitable coloring problem
topic_facet Combinatorial optimization
Equitable coloring
Tabu search
Benchmarking
Combinatorial optimization
Heuristic algorithms
Heuristic methods
Arbitrary color
Computational experiment
Equitable coloring
Exact algorithms
Graph coloring problem
Large-sized
Local search
Tabu Search heuristic
Tabu search
description The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given. Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances. © 2014 Springer International Publishing.
author Méndez Díaz, Isabel
Severin, Daniel E.
author_facet Méndez Díaz, Isabel
Severin, Daniel E.
author_sort Méndez Díaz, Isabel
title A tabu search heuristic for the equitable coloring problem
title_short A tabu search heuristic for the equitable coloring problem
title_full A tabu search heuristic for the equitable coloring problem
title_fullStr A tabu search heuristic for the equitable coloring problem
title_full_unstemmed A tabu search heuristic for the equitable coloring problem
title_sort tabu search heuristic for the equitable coloring problem
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8596LNCS_n_p347_MendezDiaz
http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p347_MendezDiaz
work_keys_str_mv AT mendezdiazisabel atabusearchheuristicfortheequitablecoloringproblem
AT severindaniele atabusearchheuristicfortheequitablecoloringproblem
AT mendezdiazisabel tabusearchheuristicfortheequitablecoloringproblem
AT severindaniele tabusearchheuristicfortheequitablecoloringproblem
_version_ 1768543993453346816

Ejemplares similares