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

2 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, Czech Republic
Duration: 13 Jul 201917 Jul 2019
https://gecco-2019.sigevo.org/index.html/HomePage

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO 2019
CountryCzech Republic
CityPrague
Period13/07/1917/07/19
OtherGECCO is the largest selective conference in the field of Evolutionary Computation, and the main conference of the Special Interest Group on Genetic and Evolutionary Computation (SIGEVO) of the Association for Computing Machinery (ACM). GECCO implements a rigorous and selective reviewing process to identify important and technically sound papers to publish. The technical program is divided into thirteen tracks reflecting all aspects of our field and chaired by experts who make the decisions on accepted papers.
Internet address

Keywords

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

Cite this