Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems

Broderick Crawford; Carlos Castro

doi:10.1007/11785231_113

Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems

Broderick Crawford, Carlos Castro

SCHOOL OF COMPUTER ENGINEERING

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

25 Scopus citations

Abstract

Set Covering Problems and Set Partitioning Problems can model several real life situations. In this paper, we solve some benchmarks of them with Ant Colony Optimization algorithms and some hybridizations of Ant Colony Optimization with Constraint Programming techniques. A lookahead mechanism allows the incorporation of information on the anticipated decisions that are beyond the immediate choice horizon. The ants solutions may contain redundant components which can be eliminated by a fine tuning after the solution, then we explore Post Processing procedures too, which consist in the identification and replacement of the columns of the ACO solution in each iteration by more effective columns. Computational results are presented showing the advantages to use additional mechanisms to Ant Colony Optimization.

Original language	English
Title of host publication	Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings
Publisher	Springer Verlag
Pages	1082-1090
Number of pages	9
ISBN (Print)	3540357483, 9783540357483
DOIs	https://doi.org/10.1007/11785231_113
State	Published - 2006
Event	8th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2006 - Zakopane, Poland Duration: 25 Jun 2006 → 29 Jun 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4029 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2006
Country/Territory	Poland
City	Zakopane
Period	25/06/06 → 29/06/06

Access to Document

10.1007/11785231_113

Cite this

Crawford, B., & Castro, C. (2006). Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems. In Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings (pp. 1082-1090). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4029 LNAI). Springer Verlag. https://doi.org/10.1007/11785231_113

Crawford, Broderick ; Castro, Carlos. / Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems. Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings. Springer Verlag, 2006. pp. 1082-1090 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{63524403f3f7487fa2cc3f9c6488571b,

title = "Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems",

abstract = "Set Covering Problems and Set Partitioning Problems can model several real life situations. In this paper, we solve some benchmarks of them with Ant Colony Optimization algorithms and some hybridizations of Ant Colony Optimization with Constraint Programming techniques. A lookahead mechanism allows the incorporation of information on the anticipated decisions that are beyond the immediate choice horizon. The ants solutions may contain redundant components which can be eliminated by a fine tuning after the solution, then we explore Post Processing procedures too, which consist in the identification and replacement of the columns of the ACO solution in each iteration by more effective columns. Computational results are presented showing the advantages to use additional mechanisms to Ant Colony Optimization.",

author = "Broderick Crawford and Carlos Castro",

year = "2006",

doi = "10.1007/11785231_113",

language = "English",

isbn = "3540357483",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1082--1090",

booktitle = "Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings",

note = "8th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2006 ; Conference date: 25-06-2006 Through 29-06-2006",

}

Crawford, B & Castro, C 2006, Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems. in Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4029 LNAI, Springer Verlag, pp. 1082-1090, 8th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2006, Zakopane, Poland, 25/06/06. https://doi.org/10.1007/11785231_113

Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems. / Crawford, Broderick; Castro, Carlos.
Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings. Springer Verlag, 2006. p. 1082-1090 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4029 LNAI).

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

TY - GEN

T1 - Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems

AU - Crawford, Broderick

AU - Castro, Carlos

PY - 2006

Y1 - 2006

N2 - Set Covering Problems and Set Partitioning Problems can model several real life situations. In this paper, we solve some benchmarks of them with Ant Colony Optimization algorithms and some hybridizations of Ant Colony Optimization with Constraint Programming techniques. A lookahead mechanism allows the incorporation of information on the anticipated decisions that are beyond the immediate choice horizon. The ants solutions may contain redundant components which can be eliminated by a fine tuning after the solution, then we explore Post Processing procedures too, which consist in the identification and replacement of the columns of the ACO solution in each iteration by more effective columns. Computational results are presented showing the advantages to use additional mechanisms to Ant Colony Optimization.

AB - Set Covering Problems and Set Partitioning Problems can model several real life situations. In this paper, we solve some benchmarks of them with Ant Colony Optimization algorithms and some hybridizations of Ant Colony Optimization with Constraint Programming techniques. A lookahead mechanism allows the incorporation of information on the anticipated decisions that are beyond the immediate choice horizon. The ants solutions may contain redundant components which can be eliminated by a fine tuning after the solution, then we explore Post Processing procedures too, which consist in the identification and replacement of the columns of the ACO solution in each iteration by more effective columns. Computational results are presented showing the advantages to use additional mechanisms to Ant Colony Optimization.

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

U2 - 10.1007/11785231_113

DO - 10.1007/11785231_113

M3 - Conference contribution

AN - SCOPUS:33746218475

SN - 3540357483

SN - 9783540357483

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1082

EP - 1090

BT - Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings

PB - Springer Verlag

T2 - 8th International Conference on Artificial Intelligence and Soft Computing, ICAISC 2006

Y2 - 25 June 2006 through 29 June 2006

ER -

Crawford B, Castro C. Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems. In Artificial Intelligence and Soft Computing - ICAISC 2006 - 8th International Conference, Proceedings. Springer Verlag. 2006. p. 1082-1090. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11785231_113

Integrating lookahead and post processing procedures with ACO for solving set partitioning and covering problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this