A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations

摘要

In this paper we present a method for finding exact solutions of the Max-Cut problem max x~T Lx such that x ∈ {-1,1}~n. We use a semidefinite relaxation combined with triangle inequalities, which we solve with the bundle method. This approach is due to Fischer, Gru-ber, Rendl, and Sotirov [12] and uses Lagrangian duality to get upper bounds with reasonable computational effort. The expensive part of our bounding procedure is solving the basic semidefinite programming relaxation of the Max-Cut problem. We review other solution approaches and compare the numerical results with our method. We also extend our experiments to unconstrained quadratic 0-1 problems and to instances of the graph bisection problem.The experiments show, that our method nearly always outperforms all other approaches. Our algorithm, which is publicly accessible through the Internet, can solve virtually any instance with about 100 variables in a routine way.