An improved merge search algorithm for the constrained pit problem in open-pit mining

Angus Kenny, Andreas T. Ernst, Xiaodong Li, Yuan Sun

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

8 Citations (Scopus)

Abstract

Conventional mixed-integer programming (MIP) solvers can struggle with many large-scale combinatorial problems, as they contain too many variables and constraints. Meta-heuristics can be applied to reduce the size of these problems by removing or aggregating variables or constraints. Merge search algorithms achieve this by generating populations of solutions, either by heuristic construction [4], or by finding neighbours to an initial solution [12]. This paper presents a merge search algorithm that improves the population generation heuristic in [12] and utilises a variable grouping heuristic that exploits the common information across a population to aggregate groups of variables in order to create a reduced subproblem. The algorithm is tested on some well known benchmarks for a complex problem called the constrained pit (CPIT) problem and it is compared to results produced by a merge search algorithm previously used on the same problem and the results published on the minelib [9] website.

Original languageEnglish
Title of host publicationProceedings of the 2019 Genetic and Evolutionary Computation Conference
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages294-302
Number of pages9
ISBN (Electronic)9781450361118
DOIs
Publication statusPublished - 13 Jul 2019
EventThe Genetic and Evolutionary Computation Conference 2019 - Prague, Czechia
Duration: 13 Jul 201917 Jul 2019
Conference number: 21st
https://gecco-2019.sigevo.org/index.html/HomePage
https://dl.acm.org/doi/proceedings/10.1145/3321707 (Proceedings)

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO 2019
Country/TerritoryCzechia
CityPrague
Period13/07/1917/07/19
Internet address

Keywords

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

Cite this