The matching problem is one of the intensely studied combinatorial optimization problems. Nevertheless, many real-world problems cannot be formulated as a pure matching problem. In this thesis we study four variants of the classical matching problem: The resource-constrained bipartite matching problem, a stochastic matching problem, a recoverable robust matching problem and the quadratic matching problem. The stochastic matching problem and the recoverable robust matching problem arise from an application to runway scheduling.

This thesis investigates integer as well as mixed-integer reformulations of these four types of matching problems. It consists of two parts. In the first part we study an exact solution approach for the resource-constrained bipartite matching problem and the stochastic matching problem. It reformulates the integer programming formulation (IP) of these problems into a mixed-integer program (MIP) that uses few integer variables. To this end, affine TU decompositions of the constraint matrix play a major role. We derive several theoretical results arising from the decomposition of the constraint matrices of matching problems with resource constraints. These findings can be extended to the stochastic matching problem as the latter can be modeled as a bipartite matching problem with a special resource constraint. In a computational study we compare different MIP reformulations of resource-constrained and stochastic matching problems with their corresponding IP formulations. We show that in several settings, running times for solving instances to optimality can significantly be reduced, when the new MIP reformulations are used. Furthermore, we examine the complexity status of the recoverable robust matching problem. In a simplified version we can model it as a bipartite matching problem with a quadratic objective in the edge variables.

In the second part we study the quadratic matching problem. It asks for a matching in a graph that optimizes a quadratic objective in the edge variables. In our solution approach, we strengthen the linearized IP formulation by cutting planes that are derived from facets of the corresponding matching problem where only one quadratic term occurs in the objective function. We present different reformulation techniques to strengthen these cutting planes. Based on these methods, we design and implement an exact branch-and-cut approach. We show that root bounds and running times for solving instances to optimality can be improved significantly, when the new approach is applied.

Das Matching-Problem ist eines der am besten untersuchten kombinatorischen Optimierungsprobleme. Viele Fragestellungen aus der Praxis, können jedoch nicht als reines Matching-Problem formuliert werden. In dieser Arbeit untersuchen wir vier Varianten des klassischen Matching-Problems: Das ressourcenbeschränkte Matching-Problem, ein stochastisches Matching-Problem, ein robust-wiederherstellbares Matching-Problem und das quadratische Matching-Problem. Das stochastische und das robust-wiederherstellbare Matching-Problem finden im Bereich der Flugplanoptimierung Anwendung.

Die Arbeit untersucht ganzzahlige sowie gemischt-ganzzahlige Reformulierungsansätze für die vier oben genannten Matching-Probleme. Sie besteht aus zwei Teilen. Im ersten Teil untersuchen wir eine exakte Lösungsmethode für das ressourcenbeschränkte und für das stochastische Matching-Problem. Die grundlegende Idee dabei ist, das ganzzahlige lineare Programm (IP) dieser beiden Probleme als ein gemischt-ganzzahliges Programm (MIP) mit nur wenigen ganzzahligen Variablen zu reformulieren. Dabei spielt das Konzept der affinen TU Dekomposition der Restriktionsmatrix eine zentrale Rolle. Wir leiten einige theoretischeResultate her, die sich bei der Dekomposition der Restriktionsmatrix von Matching-Problemen mit Ressourcenbeschränkung ergeben. Diese Ergebnisse lassen sich auf das stochastische Matching-Problem erweitern, da dieses als bipartites Matching-Problem mit einer speziellen Ressourcenbeschränkung modelliert werden kann. In einer Rechenstudie vergleichen wir verschiedene MIP Reformulierungen für ressourcenbeschränkte und stochastische Matching-Probleme mit den IP Formulierungen der beiden Probleme. Wir zeigen, dass in einigen Settings die Laufzeiten signifikant verbessert werden können, wenn die neuen MIP Reformulierungen verwendet werden. Das robust-wiederherstellbare Matching-Problem betrachten wir unter komplexitätstheoretischen Aspekten. In einer vereinfachten Version lässt sich dieses als bipartites Matching-Problem mit einer quadratischen Zielfunktion in den Kantenvariablen modellieren.

Im zweiten Teil studieren wir das quadratische Matching-Problem. Beim quadratischen Matching-Problem ist ein Matching gesucht, das eine quadratische Zielfunktion in den Kantenvariablen optimiert. Die Idee unserer Lösungsmethode ist, die linearisierte IP Formulierung durch Schnittebenen zu verstärken, die Facetten für das Matching-Problem mit nur einem quadratischen Term in der Zielfunktion induzieren. Wir geben verschiedene Reformulierungsansätze an, um die hergeleiteten Schnittebenen zu verstärken. Basierend auf diesen Methoden implementieren wir ein Branch-and-Cut Verfahren. Wir zeigen, dass durch Anwendung der neuen verstärkten Schnittebenen die Wurzelschranken und dieLaufzeiten signifikant verbessert werden können.