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

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.