Data Reductions in Combinatorial Optimization for Independence Problems

The Maximum Weight Independent Set problem is a fundamental NP-hard problem in combinatorial optimization that additionally attracts interest because of its many real-world applications. The problem asks for a subset of vertices of heighest weight in an undirected vertex-weighted graph, such that the vertices in the set are pairwise non-adjacent. While this problem is the main focus of this thesis, we also consider other independence problems, including the Maximum (Weight) 2-Packing Set, and the Maximum Weight Hypergraph b-Matching problem. An important part of solving these problems in practice is data reduction rules. This dissertation introduces new data reduction rules as well as different approaches that utilize these rules for computing high-quality solutions.
   
For the Maximum Weight Independent Set problem, we contribute several new data reduction rules and a machine learning screening approach to speed up the application of these rules. Moreover, we present heuristics that find near-optimal solutions on static graphs and a new technique to compute high-quality independent sets in the dynamic setting. This technique is also applicable to the unweighted problem and as a local search on static graphs. We also introduce multiple new data reduction rules for the Maximum 2-Packing Set problem and its weighted generalization. Combining the new data reduction rules with a reduction to the Maximum (Weight) Independent Set problem, allows us to utilize existing independent set approache resulting in several mehods to compute high-quality 2-packing sets.  Regarding the Maximum Weight b-Matching problem in hypergraphs, we present a set of new data reduction rules, a greedy strategy and a novel local search method to compute high-quality solutions.

All proposed approaches are discussed in detail and evaluated experimentally on a wide range of real-world benchmark instances. The experimental results indicate that for all of the problems discussed, using data reduction rules can significantly reduces the size of many input instances. This initial size reduction enables faster running times and can improve solution quality for all of our introduced approaches, but also for all other state-of-the-art methods tested. Furthermore, our experiments show that our new approaches outperform state-of-the-art solvers in different metrics. Overall, this dissertation demonstrates the power of using data reduction rules in different ways to solve independence problems in practice.