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 | The Genetic and Evolutionary Computation Conference, 2018 - Kyoto, Japan Duration: 15 Jul 2018 → 19 Jul 2018 http://gecco-2018.sigevo.org/index.html/tiki-index.php |
Conference
Conference | The Genetic and Evolutionary Computation Conference, 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