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

2 Citations (Scopus)

Abstract

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)
Pages316-323
Number of pages8
ISBN (Electronic)9781450356183
DOIs
Publication statusPublished - 2 Jul 2018
EventGenetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan
Duration: 15 Jul 201819 Jul 2018
http://gecco-2018.sigevo.org/index.html/tiki-index.php

Conference

ConferenceGenetic and Evolutionary Computation Conference, GECCO 2018
Abbreviated titleGECCO 2018
CountryJapan
CityKyoto
Period15/07/1819/07/18
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

Keywords

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

Cite this

Kenny, A., Li, X., & Ernst, A. T. (2018). A merge search algorithm and its application to the constrained pit problem in mining. In H. Aguirre (Ed.), GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference: 2018 Genetic and Evolutionary Computation Conference, GECCO 2018; Kyoto; Japan; 15 July 2018 through 19 July 2018 (pp. 316-323). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3205455.3205538