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 language | English |
|---|---|
| Title of host publication | GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference |
| Subtitle of host publication | 2018 Genetic and Evolutionary Computation Conference, GECCO 2018; Kyoto; Japan; 15 July 2018 through 19 July 2018 |
| Editors | Hernan Aguirre |
| Place of Publication | New York NY USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 316-323 |
| Number of pages | 8 |
| ISBN (Electronic) | 9781450356183 |
| DOIs | |
| Publication status | Published - 2 Jul 2018 |
| Event | Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan Duration: 15 Jul 2018 → 19 Jul 2018 http://gecco-2018.sigevo.org/index.html/tiki-index.php |
Conference
| Conference | Genetic and Evolutionary Computation Conference, GECCO 2018 |
|---|---|
| Abbreviated title | GECCO 2018 |
| Country | Japan |
| City | Kyoto |
| Period | 15/07/18 → 19/07/18 |
| Other | The 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
}
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 proceeding › Conference Paper › Research › peer-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 -