Ant colonies using arc consistency techniques for the set partitioning problem

Broderick Crawford, Carlos Castro

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProfessional Practice in Artificial Intelligence - IFIP 19th World Computer Congress, TC 12
Subtitle of host publicationProfessional Practice Stream
EditorsJohn Debenham
PublisherSpringer New York LLC
Pages295-301
Number of pages7
ISBN (Print)9780387346557
DOIs
StatePublished - 2006
Externally publishedYes
Event2nd Symposium on Professional Practice in Artificial Intelligence, 2006 - Santiago, Chile
Duration: 21 Aug 200624 Aug 2006

Publication series

NameIFIP Advances in Information and Communication Technology
Volume218
ISSN (Print)1868-4238

Conference

Conference2nd Symposium on Professional Practice in Artificial Intelligence, 2006
Country/TerritoryChile
CitySantiago
Period21/08/0624/08/06

Fingerprint

Dive into the research topics of 'Ant colonies using arc consistency techniques for the set partitioning problem'. Together they form a unique fingerprint.

Cite this