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

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
Kenny, Angus ; Li, Xiaodong ; Ernst, Andreas T. / A merge search algorithm and its application to the constrained pit problem in mining. 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. editor / Hernan Aguirre. New York NY USA : Association for Computing Machinery (ACM), 2018. pp. 316-323
@inproceedings{01877e4cd7844e5cb90dc9afb63f1e56,
title = "A merge search algorithm and its application to the constrained pit problem in mining",
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.",
keywords = "Applied computing, Hybrid algorithms, Merge search, Mine planning, Mixed integer programming",
author = "Angus Kenny and Xiaodong Li and Ernst, {Andreas T.}",
year = "2018",
month = "7",
day = "2",
doi = "10.1145/3205455.3205538",
language = "English",
pages = "316--323",
editor = "Hernan Aguirre",
booktitle = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Kenny, A, Li, X & Ernst, AT 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. Association for Computing Machinery (ACM), New York NY USA, pp. 316-323, Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, 15/07/18. https://doi.org/10.1145/3205455.3205538

A merge search algorithm and its application to the constrained pit problem in mining. / Kenny, Angus; Li, Xiaodong; Ernst, Andreas T.

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. ed. / Hernan Aguirre. New York NY USA : Association for Computing Machinery (ACM), 2018. p. 316-323.

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

TY - GEN

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

AU - Kenny, Angus

AU - Li, Xiaodong

AU - Ernst, Andreas T.

PY - 2018/7/2

Y1 - 2018/7/2

N2 - 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.

AB - 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.

KW - Applied computing

KW - Hybrid algorithms

KW - Merge search

KW - Mine planning

KW - Mixed integer programming

UR - http://www.scopus.com/inward/record.url?scp=85050602524&partnerID=8YFLogxK

U2 - 10.1145/3205455.3205538

DO - 10.1145/3205455.3205538

M3 - Conference Paper

SP - 316

EP - 323

BT - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

A2 - Aguirre, Hernan

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Kenny A, Li X, Ernst AT. A merge search algorithm and its application to the constrained pit problem in mining. In Aguirre H, editor, 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. New York NY USA: Association for Computing Machinery (ACM). 2018. p. 316-323 https://doi.org/10.1145/3205455.3205538