Branch-and-Cut for an SDP Relaxation of Large-Scale Minimum Bisection Problems

The minimum bisection problem (MB) is a challenging graph partitioning problem with numerous applications. Several inexact solution approaches for MB showed up in recent years. For the exact solution of large instances of MB, linear programming (LP) based methods were dominating.§§This doctoral thesis deals with the exact solution of large-scale MB via a semidefinite programming (SDP) relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope, new valid inequalities are studied. Strengthenings based on the new cluster weight polytope and polynomial separation algorithms for special cases are investigated. Computationally, the dual of the SDP relaxation of MB is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Details of the implementation are presented, including primal heuristics, branching rules, support extensions and warm start. A study showing that the chosen approach is competitive to state-of-the-art implementations using LP or SDP relaxations concludes the thesis.§§The book is aimed at researchers and practitioners in optimisation and discrete mathematics. The minimum bisection problem (MB) is a challenging graph partitioning problem with numerous applications. Several inexact solution approaches for MB showed up in recent years. For the exact solution of large instances of MB, linear programming (LP) based methods were dominating. This doctoral thesis deals with the exact solution of large-scale MB via a semidefinite programming (SDP) relaxation in a branch-and-cut framework. After reviewing known results on the underlying bisection cut polytope, new valid inequalities are studied. Strengthenings based on the new cluster weight polytope and polynomial separation algorithms for special cases are investigated. Computationally, the dual of the SDP relaxation of MB is tackled in its equivalent form as an eigenvalue optimisation problem with the spectral bundle method. Details of the implementation are presented, including primal heuristics, branching rules, support extensions and warm start. A study showing that the chosen approach is competitive to state-of-the-art implementations using LP or SDP relaxations concludes the thesis. The book is aimed at researchers and practitioners in optimisation and discrete mathematics.