### Abstract

Ant colony optimisation has traditionally been used to solve problems that have few/light constraints or no constraints at all. Algorithms to maintain and restore feasibility have been successfully applied to such problems. Set partitioning is a very constrained combinatorial optimisation problem, for which even feasible solutions are difficult to construct. In this paper a binary ant colony optimisation framework is applied to this problem. To increase its effectiveness, feasibility restoration, solution improvement algorithms and candidate set strategies are added. These algorithms can be applied to complete solution vectors and as such can be used by any solver. Moreover, the principles of the support algorithms may be applied to other constrained problems. The overall results indicate that the ant colony optimisation algorithm can efficiently solve small to medium sized problems. It is envisaged that in future research parallel computation could be used to simultaneouly reduce solver time while increasing solution quality.

Original language | English |
---|---|

Title of host publication | Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 |

Pages | 110-116 |

Number of pages | 7 |

DOIs | |

Publication status | Published - 2010 |

Event | 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 - Brisbane, QLD, Australia Duration: 7 Dec 2010 → 10 Dec 2010 |

### Conference

Conference | 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010 |
---|---|

Country | Australia |

City | Brisbane, QLD |

Period | 7/12/10 → 10/12/10 |

### Fingerprint

### Cite this

*Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010*(pp. 110-116). [5693150] https://doi.org/10.1109/eScienceW.2010.27

}

*Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010.*, 5693150, pp. 110-116, 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010, Brisbane, QLD, Australia, 7/12/10. https://doi.org/10.1109/eScienceW.2010.27

**Modifications and additions to ant colony optimisation to solve the set partitioning problem.** / Randall, Marcus; Lewis, Andrew.

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

TY - GEN

T1 - Modifications and additions to ant colony optimisation to solve the set partitioning problem

AU - Randall, Marcus

AU - Lewis, Andrew

PY - 2010

Y1 - 2010

N2 - Ant colony optimisation has traditionally been used to solve problems that have few/light constraints or no constraints at all. Algorithms to maintain and restore feasibility have been successfully applied to such problems. Set partitioning is a very constrained combinatorial optimisation problem, for which even feasible solutions are difficult to construct. In this paper a binary ant colony optimisation framework is applied to this problem. To increase its effectiveness, feasibility restoration, solution improvement algorithms and candidate set strategies are added. These algorithms can be applied to complete solution vectors and as such can be used by any solver. Moreover, the principles of the support algorithms may be applied to other constrained problems. The overall results indicate that the ant colony optimisation algorithm can efficiently solve small to medium sized problems. It is envisaged that in future research parallel computation could be used to simultaneouly reduce solver time while increasing solution quality.

AB - Ant colony optimisation has traditionally been used to solve problems that have few/light constraints or no constraints at all. Algorithms to maintain and restore feasibility have been successfully applied to such problems. Set partitioning is a very constrained combinatorial optimisation problem, for which even feasible solutions are difficult to construct. In this paper a binary ant colony optimisation framework is applied to this problem. To increase its effectiveness, feasibility restoration, solution improvement algorithms and candidate set strategies are added. These algorithms can be applied to complete solution vectors and as such can be used by any solver. Moreover, the principles of the support algorithms may be applied to other constrained problems. The overall results indicate that the ant colony optimisation algorithm can efficiently solve small to medium sized problems. It is envisaged that in future research parallel computation could be used to simultaneouly reduce solver time while increasing solution quality.

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

U2 - 10.1109/eScienceW.2010.27

DO - 10.1109/eScienceW.2010.27

M3 - Conference contribution

SN - 9780769542959

SP - 110

EP - 116

BT - Proceedings - 6th IEEE International Conference on e-Science Workshops, e-ScienceW 2010

ER -