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

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

doi:10.1145/3321707.3321812

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

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

School of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	Proceedings of the 2019 Genetic and Evolutionary Computation Conference
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	294-302
Number of pages	9
ISBN (Electronic)	9781450361118
DOIs	https://doi.org/10.1145/3321707.3321812
Publication status	Published - 13 Jul 2019
Event	The Genetic and Evolutionary Computation Conference 2019 - Prague, Czech Republic Duration: 13 Jul 2019 → 17 Jul 2019 Conference number: 21st https://gecco-2019.sigevo.org/index.html/HomePage https://dl.acm.org/doi/proceedings/10.1145/3321707 (Proceedings)

Conference

Conference	The Genetic and Evolutionary Computation Conference 2019
Abbreviated title	GECCO 2019
Country/Territory	Czech Republic
City	Prague
Period	13/07/19 → 17/07/19
Other	GECCO 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	https://gecco-2019.sigevo.org/index.html/HomePage https://dl.acm.org/doi/proceedings/10.1145/3321707 (Proceedings)

Keywords

Applied computing
Hybrid algorithms
Merge search
Mine planning
Mixed integer programming

Access to Document

10.1145/3321707.3321812

Cite this

@inproceedings{c70e31fc297d4ed9ad0094e202a620a6,

title = "An improved merge search algorithm for the constrained pit problem in open-pit mining",

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.",

keywords = "Applied computing, Hybrid algorithms, Merge search, Mine planning, Mixed integer programming",

author = "Angus Kenny and Ernst, {Andreas T.} and Xiaodong Li and Yuan Sun",

year = "2019",

month = jul,

day = "13",

doi = "10.1145/3321707.3321812",

language = "English",

pages = "294--302",

booktitle = "Proceedings of the 2019 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

note = "The Genetic and Evolutionary Computation Conference 2019, GECCO 2019 ; Conference date: 13-07-2019 Through 17-07-2019",

url = "https://gecco-2019.sigevo.org/index.html/HomePage, https://dl.acm.org/doi/proceedings/10.1145/3321707",

}

Kenny, A, Ernst, AT, Li, X & Sun, Y 2019, An improved merge search algorithm for the constrained pit problem in open-pit mining. in Proceedings of the 2019 Genetic and Evolutionary Computation Conference. Association for Computing Machinery (ACM), New York NY USA, pp. 294-302, The Genetic and Evolutionary Computation Conference 2019, Prague, Czech Republic, 13/07/19. https://doi.org/10.1145/3321707.3321812

An improved merge search algorithm for the constrained pit problem in open-pit mining. / Kenny, Angus; Ernst, Andreas T.; Li, Xiaodong; Sun, Yuan.

Proceedings of the 2019 Genetic and Evolutionary Computation Conference. New York NY USA : Association for Computing Machinery (ACM), 2019. p. 294-302.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

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

AU - Kenny, Angus

AU - Ernst, Andreas T.

AU - Li, Xiaodong

AU - Sun, Yuan

N1 - Conference code: 21st

PY - 2019/7/13

Y1 - 2019/7/13

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

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

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=85072348088&partnerID=8YFLogxK

U2 - 10.1145/3321707.3321812

DO - 10.1145/3321707.3321812

M3 - Conference Paper

SP - 294

EP - 302

BT - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

T2 - The Genetic and Evolutionary Computation Conference 2019

Y2 - 13 July 2019 through 17 July 2019

ER -

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Hybrid methods with decomposition for large scale optimization

Cite this

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Projects

Hybrid methods with decomposition for large scale optimization

Cite this