A tabu search heuristic for the equitable coloring problem

Mostrar todas las versiones(2)

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, I., Nasini, G., Severín, D., Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
Formato: SER
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: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 todo:paper_03029743_v8596LNCS_n_p347_MendezDiaz
record_format dspace
spelling todo:paper_03029743_v8596LNCS_n_p347_MendezDiaz2023-10-03T15:19:38Z A tabu search heuristic for the equitable coloring problem Méndez Díaz, I. Nasini, G. Severín, D. Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, I.
Nasini, G.
Severín, D.
Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
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.
format SER
author Méndez Díaz, I.
Nasini, G.
Severín, D.
Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
author_facet Méndez Díaz, I.
Nasini, G.
Severín, D.
Associacao Portuguesa de Investigacao Operacional; de Lisboa, Centro de Investigacao Operacional; Faculdade de Ciencias da Universidade; Fundacao para a Ciencia e a Tecnologia; Instituto Nacional de Estatistica; Universite Paris-Dauphine, LAMSADE
author_sort Méndez Díaz, I.
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
url http://hdl.handle.net/20.500.12110/paper_03029743_v8596LNCS_n_p347_MendezDiaz
work_keys_str_mv AT mendezdiazi atabusearchheuristicfortheequitablecoloringproblem
AT nasinig atabusearchheuristicfortheequitablecoloringproblem
AT severind atabusearchheuristicfortheequitablecoloringproblem
AT associacaoportuguesadeinvestigacaooperacionaldelisboacentrodeinvestigacaooperacionalfaculdadedecienciasdauniversidadefundacaoparaacienciaeatecnologiainstitutonacionaldeestatisticauniversiteparisdauphinelamsade atabusearchheuristicfortheequitablecoloringproblem
AT mendezdiazi tabusearchheuristicfortheequitablecoloringproblem
AT nasinig tabusearchheuristicfortheequitablecoloringproblem
AT severind tabusearchheuristicfortheequitablecoloringproblem
AT associacaoportuguesadeinvestigacaooperacionaldelisboacentrodeinvestigacaooperacionalfaculdadedecienciasdauniversidadefundacaoparaacienciaeatecnologiainstitutonacionaldeestatisticauniversiteparisdauphinelamsade tabusearchheuristicfortheequitablecoloringproblem
_version_ 1807317343657787392

Ejemplares similares