Merge Search: a hybrid meta-heuristic for solving constrained optimisation problems
Creators: name: KENNY, Angus
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 460203
subject: Evolutionary computation
classificationCode: 490304
subject: Optimisation

description: Exact methods such as mixed integer programming (MIP) are useful for solving combinatorial optimisation problems as they provide proof that the solutions they produce are optimal. However, the time needed to solve problems using these techniques increases exponentially with the size of the instances; with many real-world problems, sometimes containing many thousands (or even millions) of variables, becoming intractable. Conversely, meta-heuristics are adept at finding feasible solutions to problems in a reasonable time, but sacrifice the guarantee of optimality in order to achieve this. To this end, a relatively new area of research has opened up concerning the hybridisation of meta-heuristics with mathematical programming to create a new strain of algorithms called hybrid meta-heuristics or matheuristics that harness the strengths of both of these types of algorithms.

This thesis presents a new hybrid meta-heuristic designed to solve large-scale combinatorial problems, called merge search. Merge search is an iterative decomposition algorithm which operates by grouping variables that share common values across a population of solutions to create a reduced version of the original problem. It can be thought of as a generalisation of the crossover operator used in many evolutionary algorithms; however, instead of combining two solutions to create a single offspring solution, the sub-space that is spanned by the entire population is searched for the optimal way to combine all solutions by a reduced sub-problem.

Merge search is introduced here as a general matheuristic --- that is, a meta-heuristic that works generically on any mathematical programming formulation. The general nature of the technique is demonstrated by applying it to two, very different, NP-Hard problems: The first is the constrained pit limit (CPIT) problem which is an abstraction of the real-world problem of planning an open-pit mine. The second problem is the Steiner tree problem in graphs (STPG). This problem is a classic problem in networks, the decision variant of which is one of Karp's original 21 NP-Complete problems.

In order to solve the CPIT problem using merge search, a heuristic method of constructing feasible solutions is described; along with a local-search operator for producing a population in the neighbourhood of a given solution. A modified MIP formulation is also given for the problem which incorporates the new merge variables.

The STPG is a much more researched problem than CPIT and as such there already exist methods for generating feasible solutions and methods for finding neighbouring solutions. These existing techniques are described and expanded upon here with two new methods of generating feasible solutions, one deterministic and one random. A local-search operator which extends what is already available in the literature is also described and a modified MIP formulation that uses merge variables is given.

All heuristic search methods have to balance the tension between aspects of diversification and intensification; the former determines the best area to search and the latter refines the solutions found there. The experiments conducted on the CPIT problem focus on exploring the intensification of merge search by altering various properties and functionalities of the algorithm; whereas, the experiments on the STPG focus on the diversification aspects and how the size and distribution of the groupings can be controlled to affect the outcome of the search.

One significant advantage of merge search is that it is problem agnostic, and operates directly on the binary decision variables of the problem. Another advantage is that merge search requires no explicit knowledge of the structure of the problem to operate; the variables being grouped according to their interaction across the population and the problem structure implicit in these variable groupings. Through experiments on these difficult problems, merge search is shown to produce state-of-the-art results and is therefore potentially a useful new tool in the suite of meta-heuristic algorithms.