Algorithm Engineering and Integer Programming for the Maximum Cut Problem

Abstract

The maximum cut problem, MaxCut for short, is one of the fundamental problems in combinatorial optimization. It is part of a large family of graph partitioning problems that ask for a division of all vertices of the graph into disjoint sets. In its optimization form MaxCut is about finding a bipartition that maximizes the value of a cut. A cut in the context of a vertex partition is defined as the set of edges connecting vertices of different partitions. The value of a cut is the sum of all weights associated with the edges of the cut. <br/> Although MaxCut allows for a compact description, it has highly relevant modeling power. Many real-world applications for MaxCut have been described in the literature over the years; these range from chip design to scheduling sports leagues and, more recently, the benchmarking of certain quantum algorithms and computers. Depending on the application, good solutions do not suffice and practitioners and researchers are interested in optimal solutions. Unfortunately, MaxCut is NP-hard in general, and it is still unknown whether we can solve NP-hard problems fast, that is, in time polynomial in the input size. However, practical algorithms for solving MaxCut to optimality have been designed in the past, and this thesis aims to improve them and develop new ones. We focus especially on techniques for sparse graphs, as real-world instances often turn out to be sparse. <br/> An important way to speed up algorithms for hard problems is to reduce the search space before even exploring it. The process of performing these reductions without sacrificing optimal solutions is called presolving. We develop new presolving algorithms for MaxCut in three categories. One of these is based on vertex separators that have not been explicitly considered for MaxCut so far. <br/> For exploring and further pruning of the search space for MaxCut we resort to integer programming and the branch-and-cut algorithm, which has yielded good results for exact MaxCut algorithms in the past. We extend previous work and suggest a refined integer program. This model has implications for other modules part of the branch-and-cut algorithm that we present in detail. Examples are the generation of cutting planes and problem-specific branching rules. From these we derive new and concrete algorithms that can be employed in MaxCut solvers based on branch-and-cut. <br/> To evaluate the practical relevance of our new techniques, we perform elaborate experimental studies and compare them against the state of the art. For this we carefully engineered a new solver that contains state-of-the-art techniques and our new ones. The solver is competitive to the fastest MaxCut solver in general and clearly outperforms the state of the art for certain inputs. In detailed ablation studies, we track these improvements down to our new techniques. Especially, our presolving and cutting plane generation offers significant speed-up potential of up to one order of magnitude over the state of the art.