Constraint programming can help ants solving highly constrainted combinatorial problems

Broderick Crawford; Carlos Castro; Eric Monfroy

Constraint programming can help ants solving highly constrainted combinatorial problems

Broderick Crawford, Carlos Castro, Eric Monfroy

SCHOOL OF COMPUTER ENGINEERING

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies
Publisher	Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC)
Pages	380-383
Number of pages	4
ISBN (Print)	9789898111517
State	Published - 2008
Event	ICSOFT 2008 - 3rd International Conference on Software and Data Technologies - Porto, Portugal Duration: 5 Jul 2008 → 8 Jul 2008

Publication series

Name	ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies
Volume	PL/DPS/KE

Conference

Conference	ICSOFT 2008 - 3rd International Conference on Software and Data Technologies
Country/Territory	Portugal
City	Porto
Period	5/07/08 → 8/07/08

Keywords

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

Cite this

Crawford, B., Castro, C., & Monfroy, E. (2008). Constraint programming can help ants solving highly constrainted combinatorial problems. In ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies (pp. 380-383). (ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies; Vol. PL/DPS/KE). Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC).

Crawford, Broderick ; Castro, Carlos ; Monfroy, Eric. / Constraint programming can help ants solving highly constrainted combinatorial problems. ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies. Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC), 2008. pp. 380-383 (ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies).

@inproceedings{feb3b8ac92e148b5a25adb53a2c7393d,

title = "Constraint programming can help ants solving highly constrainted combinatorial problems",

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.",

keywords = "Ant Colony Optimization (ACO), Arc consistency (AC), Constraint Programming (CP), Constraint propagation, Set Partitioning Problem (SPP)",

author = "Broderick Crawford and Carlos Castro and Eric Monfroy",

year = "2008",

language = "English",

isbn = "9789898111517",

series = "ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies",

publisher = "Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC)",

pages = "380--383",

booktitle = "ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies",

note = "ICSOFT 2008 - 3rd International Conference on Software and Data Technologies ; Conference date: 05-07-2008 Through 08-07-2008",

}

Crawford, B, Castro, C & Monfroy, E 2008, Constraint programming can help ants solving highly constrainted combinatorial problems. in ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies. ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies, vol. PL/DPS/KE, Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC), pp. 380-383, ICSOFT 2008 - 3rd International Conference on Software and Data Technologies, Porto, Portugal, 5/07/08.

Constraint programming can help ants solving highly constrainted combinatorial problems. / Crawford, Broderick; Castro, Carlos; Monfroy, Eric.
ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies. Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC), 2008. p. 380-383 (ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies; Vol. PL/DPS/KE).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Constraint programming can help ants solving highly constrainted combinatorial problems

AU - Crawford, Broderick

AU - Castro, Carlos

AU - Monfroy, Eric

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Ant Colony Optimization (ACO)

KW - Arc consistency (AC)

KW - Constraint Programming (CP)

KW - Constraint propagation

KW - Set Partitioning Problem (SPP)

UR - http://www.scopus.com/inward/record.url?scp=55849139864&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:55849139864

SN - 9789898111517

T3 - ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies

SP - 380

EP - 383

BT - ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies

PB - Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC)

T2 - ICSOFT 2008 - 3rd International Conference on Software and Data Technologies

Y2 - 5 July 2008 through 8 July 2008

ER -

Crawford B, Castro C, Monfroy E. Constraint programming can help ants solving highly constrainted combinatorial problems. In ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies. Inst. for Syst. and Technol. of Inf., Control and Commun. (INSTICC). 2008. p. 380-383. (ICSOFT 2008 - Proceedings of the 3rd International Conference on Software and Data Technologies).

Constraint programming can help ants solving highly constrainted combinatorial problems

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this