Relaxations and Solutions for the Minimum Graph Bisection Problem

The minimum graph bisection problem is a special kind of a graph partitioning problem, where the nodes of a weighted graph are divided into two subsets with prescribed capacity, and the weighted sum of edges joining nodes in different subsets is minimized. Due to the knapsack condition on the weight of the node subsets the problem is NP-hard. It has a variety of applications, for instance in the design of electronic circuits and devices. In this thesis we investigate current efficient optimization methods to solve to optimality the minimum graph bisection problem. This combinatorial optimization problem can be modeled by means of linear as well as quadratic integer programming. Each formulation leads to a different kind of approximation, in form of a relaxation, and thus different computational methods applied for their solution. Nevertheless, the feasible sets in each representation are in one-to-one correspondence under an affine transformation. Thus the convex hull of the feasible points, the so called bisection cut polytope, is a common object to study. The tightest possible description of this polytope can be utilized to improve the approximations. We incorporate the separation algorithms for the obtained new classes of valid inequalities in a branch-and-cut framework and investigate their interaction with linear and semidefinite relaxations using instances coming from VLSI design and scientific computations as well as random graphs. Generally only the linear relaxation benefits from the new inequalities. Although they also improve the bounds delivered by semidefinite relaxation, the separation time significantly slows down the solution process. The semidefinite relaxation seems to outperform the linear one due to a weakness of the primal methods applied to the linear relaxation. By means of random instances we show that combinations of the linear and the semidefinite relaxation within one solution process pay off.