Integer and Mixed-Integer Reformulations of Stochastic, Resource-Constrained, and Quadratic Matching Problems
Lena Hupp · OPUS FAU (Kooperativer Bibliotheksverbund Berlin-Brandenburg (KOBV), on behalf of the Universitätsbibliothek Erlangen-Nürnberg) · 2017
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.