Partitioning through projections: strong SDP bounds for large graph partition problems
From MaRDI portal
Publication:6109293
Abstract: The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both positive semidefinite and nonnegative, strengthened by additional polyhedral cuts for two variations of the GPP: the -equipartition and the graph bisection problem. After reducing the size of the relaxations by facial reduction, we solve them by a cutting-plane algorithm that combines an augmented Lagrangian method with Dykstra's projection algorithm. Since many components of our algorithm are general, the algorithm is suitable for solving various DNN relaxations with a large number of cutting planes. We are the first to show the power of DNN relaxations with additional cutting planes for the GPP on large benchmark instances up to 1,024 vertices. Computational results show impressive improvements in strengthened DNN bounds.
Recommendations
- An efficient semidefinite programming relaxation for the graph partition problem
- SDP-based bounds for graph partition via extended ADMM
- Semidefinite programming relaxations for the graph partitioning problem
- Graph bisection revisited
- Semidefinite programming and eigenvalue bounds for the graph partition problem
Cites work
- A better upper bound on the bisection width of de Bruijn networks (extended abstract)
- A boundary point method to solve semidefinite programs
- A branch-and-cut algorithm for the equicut problem
- A cutting plane algorithm for a clustering problem
- A cyclic projection algorithm via duality
- A projection technique for partitioning the nodes of a graph
- A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem
- A VLSI decomposition of the deBruijn graph
- ADMM for the SDP relaxation of the QAP
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An Algorithm for Restricted Least Squares Regression
- An efficient semidefinite programming relaxation for the graph partition problem
- An exact algorithm for graph partitioning
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Graph bisection revisited
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3973706 (Why is no real title available?)
- scientific article; zbMATH DE number 1182569 (Why is no real title available?)
- scientific article; zbMATH DE number 2196287 (Why is no real title available?)
- Hybrid evolutionary algorithms for graph coloring
- Lower bounds for the bandwidth problem
- Lower Bounds for the Partitioning of Graphs
- LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
- Mathematical formulation of quantum circuit design problems in networks of quantum computers
- Matrices Associated With the Hitchcock Problem
- Non-stationary Douglas-Rachford and alternating direction method of multipliers: adaptive step-sizes and convergence
- On semidefinite programming relaxations of maximum \(k\)-section
- On solving the quadratic shortest path problem
- On the Slater condition for the SDP relaxations of nonconvex sets
- Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
- Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
- Scalable semidefinite programming
- SDP relaxations for some combinatorial optimization problems
- SDP-based bounds for graph partition via extended ADMM
- SDP-Based Bounds for the Quadratic Cycle Cover Problem via Cutting-Plane Augmented Lagrangian Methods and Reinforcement Learning
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Semidefinite programming relaxations for the graph partitioning problem
- Solving k-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method
- Solving Graph Bisection Problems with Semidefinite Programming
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Some simplified NP-complete graph problems
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The Maximum k-Colorable Subgraph Problem and Related Problems
- The MIN-cut and vertex separator problem
- The node capacitated graph partitioning problem: A computational study
- The partition problem
Cited in
(5)- SDP-based bounds for graph partition via extended ADMM
- Strong SDP based bounds on the cutwidth of a graph
- Computing the edge expansion of a graph using semidefinite programming
- Spanning and splitting: integer semidefinite programming for the quadratic minimum spanning tree problem
- Edge expansion of a graph: SDP-based computational strategies
This page was built for publication: Partitioning through projections: strong SDP bounds for large graph partition problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109293)
