TY - GEN
T1 - Ant colonies using arc consistency techniques for the set partitioning problem
AU - Crawford, Broderick
AU - Castro, Carlos
N1 - Publisher Copyright:
© 2006 by International Federation for Information Processing. All rights reserved.
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=68049114716&partnerID=8YFLogxK
U2 - 10.1007/978-0-387-34749-3_31
DO - 10.1007/978-0-387-34749-3_31
M3 - Conference contribution
AN - SCOPUS:68049114716
SN - 9780387346557
T3 - IFIP Advances in Information and Communication Technology
SP - 295
EP - 301
BT - Professional Practice in Artificial Intelligence - IFIP 19th World Computer Congress, TC 12
A2 - Debenham, John
PB - Springer New York LLC
T2 - 2nd Symposium on Professional Practice in Artificial Intelligence, 2006
Y2 - 21 August 2006 through 24 August 2006
ER -