A merge search algorithm and its application to the constrained pit problem in mining

Angus Kenny, Xiaodong Li, Andreas T. Ernst

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

3 Citations (Scopus)


Many large-scale combinatorial problems contain too many variables and constraints for conventional mixed-integer programming (MIP) solvers to manage. To make the problems easier for the solvers to handle, various meta-heuristic techniques can be applied to reduce the size of the search space, by removing, or aggregating, variables and constraints. A novel meta-heuristic technique is presented in this paper called merge search, which takes an initial solution and uses the information from a large population of neighbouring solutions to determine promising areas of the search space to focus on. The population is merged to produce a restricted sub-problem, with far fewer variables and constraints, which can then be solved by a MIP solver. Merge search is applied to a complex problem from open-pit mining called the constrained pit (CPIT) problem, and compared to current state-of-the-art results on well known benchmark problems minelib [7] and is shown to give better quality solutions in five of the six instances.

Original languageEnglish
Title of host publicationGECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
Subtitle of host publication2018 Genetic and Evolutionary Computation Conference, GECCO 2018; Kyoto; Japan; 15 July 2018 through 19 July 2018
EditorsHernan Aguirre
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Electronic)9781450356183
Publication statusPublished - 2 Jul 2018
EventThe Genetic and Evolutionary Computation Conference, 2018 - Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018


ConferenceThe Genetic and Evolutionary Computation Conference, 2018
Abbreviated titleGECCO 2018
OtherThe Genetic and Evolutionary Computation Conference (GECCO) presents the latest high-quality results in genetic and evolutionary computation since 1999. Topics include: genetic algorithms, genetic programming, ant colony optimization and swarm intelligence, complex systems (artificial life/robotics/evolvable hardware/generative and developmental systems/artificial immune systems), digital entertainment technologies and arts, evolutionary combinatorial optimization and metaheuristics, evolutionary machine learning, evolutionary multiobjective optimization, evolutionary numerical optimization, real world applications, search-based software engineering, theory and more.
Internet address


  • Applied computing
  • Hybrid algorithms
  • Merge search
  • Mine planning
  • Mixed integer programming

Cite this