Optimization Online


A Strictly Contractive Peaceman-Rachford Splitting Method for the Doubly Nonnegative Relaxation of the Minimum Cut Problem

Xinxin Li(xinxinli***at***jlu.edu.cn)
Ting Kei Pong(tk.pong***at***polyu.edu.hk)
Hao Sun(h34sun***at***uwaterloo.ca)
Henry Wolkowicz(hwolkowicz***at***uwaterloo.ca)

Abstract: 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.

Keywords: Semidefinite relaxation, doubly nonnegative relaxation, min-cut, Peaceman-Rachford splitting method, facial reduction, graph partitioning, vertex separator

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: Department of Combinatorics & Optimization, University of Waterloo, Canada,10/2019

Download: [PDF]

Entry Submitted: 10/22/2019
Entry Accepted: 10/22/2019
Entry Last Modified: 10/22/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society