< Back to previous page
Publication
Constructive matheuristics for combinatorial optimization problems
Book - Dissertation
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 presents
a 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.
a 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.
Publication year:2021
Accessibility:Open