The minimum cut problem, MC, and the special case of the vertex separator problem, consists in partitioning the set of nodes of a graph G into k subsets of given sizes in order to minimize the number of edges cut after removing the k-th set. Previous work on this topic uses eigenvalue, semidefinite programming, SDP, and doubly nonnegative, DNN, bounds, with the latter being strong but expensive. In this paper, we derive strengthened SDP and DNN relaxations, and propose a scalable algorithmic approach for efficiently evaluating both upper and lower bounds. Our stronger relaxations are based on a new gangster set, and we demonstrate how facial reduction, FR, fits in well to allow for regularized relaxations. Moreover, the FR appears to be perfectly well suited for a natural splitting of variables and thus for the application of splitting methods. Here, we adopt the strictly contractive Peaceman-Rachford splitting method, sPRSM. We discuss how useful redundant constraints can be brought back to the subproblems involved to empirically accelerate the sPRSM. We also propose new strategies for obtaining lower bounds and upper bounds of the optimal value of MC from the iterates of the sPRSM to help the algorithm terminate early. Numerical experiments on random datasets and vertex separator problems comparing with other existing approaches demonstrate the efficiency and robustness of the proposed method.
Citation
Department of Combinatorics & Optimization, University of Waterloo, Canada,10/2019