The bee-benders hybrid algorithm with application to transmission expansion planning

Cameron A.G. MacRae, Melih Ozlen, Andreas T. Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

2 Citations (Scopus)

Abstract

This paper introduces a novel hybrid optimisation algorithm that combines elements of both metaheuristic search and integer programming. This new matheuristic combines elements of Benders decomposition and the Bees Algorithm, to create the Bee-Benders Hybrid Algorithm (BBHA) which retains many of the advantages of both methods. Specifically, it is designed to be easily parallelisable, to produce good solutions quickly while still retaining a guarantee of optimality when run for a sufficiently long time. The algorithm is tested using a transmission network expansion and energy storage planning model, a challenging and very large scale mixed integer linear programming problem. The BBHA is shown to be a highly effective hybrid matheuristic algorithm for this challenging combinatorial optimisation problem that performs at least as well as either Benders decomposition or the Bees Algorithm on their own, and significantly improves upon the individual approaches in many instances. While the paper demonstrates the effectiveness on an electricity network planning problem, the algorithm could be readily applied to any mixed integer linear program, and is expected to work particularly well whenever this has a structure that is amenable to Benders decomposition.

Original languageEnglish
Title of host publicationGECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
Subtitle of host publication2021 Genetic and Evolutionary Computation Conference, GECCO 2021Virtual, Online10 July 2021 through 14 July 2021Code 169982
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages1275-1282
Number of pages8
ISBN (Electronic)9781450383516
DOIs
Publication statusPublished - 7 Jul 2021
EventThe Genetic and Evolutionary Computation Conference 2021 - Online, Lille, France
Duration: 10 Jul 202114 Jul 2021
Conference number: 23rd
https://dl.acm.org/doi/proceedings/10.1145/3449639 (Proceedings)

Publication series

NameGECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2021
Abbreviated titleGECCO 2021
Country/TerritoryFrance
CityLille
Period10/07/2114/07/21
Internet address

Keywords

  • decomposition
  • matheuristic
  • optimisation
  • power transmission

Cite this