Constructive matheuristics for combinatorial optimization problems

Combinatorial optimization is a branch of applied mathematics with a wide
range of applications in the area of operations research. The defining
characteristic of combinatorial optimization problems is that they seek to
determine the optimal solution for a problem from a finite set of possibilities.
Such problems may seem trivial to state, but can often prove extremely difficult
to solve. Despite the existence of strong mathematical programming techniques
for most combinatorial optimization problems, efficient heuristic strategies are
often necessary to handle large, real-world instances. This is partly due to
the fact that several such problems are NP-hard and that current industrial
standards require quick decision-making.
The research presented in this thesis is motivated by the recent success
of mixed integer programming-based heuristics. These hybrid heuristics
explore how commercial MIP-solvers can be incorporated into traditional
heuristics to design intelligent optimization algorithms. This thesis presentsa hybrid approach called constructive matheuristics (CMH) that utilize the
mathematical programming aspects of a given problem to design a suitable
heuristic approach. CMH is a decomposition-based approach best suited to
large-scale real-world optimization problems modeled as integer programming
problems. The idea is to employ decomposition strategies designed in
accordance with the integer programming formulation of a given problem in
order to exploit its underlying mathematical structure.
Beginning with a basic CMH approach applied to a sports scheduling problem,
the thesis explores how the design parameters proposed for the CMH interact
with the problem’s structure. The insights gained are subsequently employed
to improve the proposed CMH and the resulting approach is further tested on a
challenging employee scheduling problem. Aside from studying the algorithm’s
characteristics, the thesis also explores how different decomposition strategies
compare when used within CMHs. In order to achieve this, the final stage of
the thesis tests the proposed CMH on the vertex coloring problem, a problem that is very difficult to decompose. This is a leap from the problems previously
considered, given that both of those had a natural time structure. Moreover,
as a problem that can be viewed as a generalization of those two preceding
problems, it offers opportunities to investigate and generalize various aspects
of the CMH proposed. As a result of the experiments conducted, significant
insights are gained regarding why certain decompositions outperform others for
the problems studied in this thesis.