Ant colonies using arc consistency techniques for the set partitioning problem

Broderick Crawford, Carlos Castro

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

4 Citas (Scopus)

Resumen

In this paper, we solve some benchmarks of Set Covering Problem and Equality Constrained Set Covering or Set Partitioning Problem. The resolution techniques used to solve them were Ant Colony Optimization algorithms and Hybridizations of Ant Colony Optimization with Constraint Programming techniques based on Arc Consistency. The concept of Arc Consistency plays an essential role in constraint satisfaction as a problem simplification operation and as a tree pruning technique during search through the detection of local inconsistencies with the uninstantiated variables. In the proposed hybrid algorithms, we explore the addition of this mechanism in the construction phase of the ants so they can generate only feasible partial solutions. Computational results are presented showing the advantages to use this kind of additional mechanisms to Ant Colony Optimization in strongly constrained problems where pure Ant Algorithms are not successful.

Idioma originalInglés
Título de la publicación alojadaProfessional Practice in Artificial Intelligence - IFIP 19th World Computer Congress, TC 12
Subtítulo de la publicación alojadaProfessional Practice Stream
EditoresJohn Debenham
EditorialSpringer New York LLC
Páginas295-301
Número de páginas7
ISBN (versión impresa)9780387346557
DOI
EstadoPublicada - 2006
Evento2nd Symposium on Professional Practice in Artificial Intelligence, 2006 - Santiago, Chile
Duración: 21 ago. 200624 ago. 2006

Serie de la publicación

NombreIFIP Advances in Information and Communication Technology
Volumen218
ISSN (versión impresa)1868-4238

Conferencia

Conferencia2nd Symposium on Professional Practice in Artificial Intelligence, 2006
País/TerritorioChile
CiudadSantiago
Período21/08/0624/08/06

Huella

Profundice en los temas de investigación de 'Ant colonies using arc consistency techniques for the set partitioning problem'. En conjunto forman una huella única.

Citar esto