Constraint programming can help ants solving highly constrainted combinatorial problems

Broderick Crawford, Carlos Castro, Eric Monfroy

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

1 Scopus citations

Abstract

In this paper, we focus on the resolution of Set Partitioning Problem. We try to solve it with Ant Colony Optimization algorithms and Hybridizations of Ant Colony Optimization with Constraint Programming techniques. We recognize the difficulties of pure Ant Algorithms solving strongly constrained problems. Therefore, we explore the addition of Constraint Programming mechanisms in the construction phase of the ants so they can complete their solutions. Computational results solving some test instances are presented showing the advantages to use this kind of hybridization.

Original languageEnglish
Title of host publicationICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies
PublisherInst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC)
Pages380-383
Number of pages4
ISBN (Print)9789898111517
StatePublished - 2008
Externally publishedYes
EventICSOFT 2008 - 3rd International Conference on Software and Data Technologies - Porto, Portugal
Duration: 5 Jul 20088 Jul 2008

Publication series

NameICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies
VolumePL/DPS/KE

Conference

ConferenceICSOFT 2008 - 3rd International Conference on Software and Data Technologies
Country/TerritoryPortugal
CityPorto
Period5/07/088/07/08

Keywords

  • Ant Colony Optimization (ACO)
  • Arc consistency (AC)
  • Constraint Programming (CP)
  • Constraint propagation
  • Set Partitioning Problem (SPP)

Fingerprint

Dive into the research topics of 'Constraint programming can help ants solving highly constrainted combinatorial problems'. Together they form a unique fingerprint.

Cite this