A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem

DOI10.1007/978-3-540-68891-4_8zbMath1143.90397OpenAlexW1529261801MaRDI QIDQ3503843

Michael Armbruster, Marzena Fügenschuh, Alexander Martin, Christoph Helmberg

Publication date: 10 June 2008

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-68891-4_8

zbMATH Keywords

polyhedral combinatoricssemidefinite programscutting plane algorithmsBranch and cut algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Matrix Relaxations in Combinatorial Optimization, An overview of graph covering and partitioning, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, On semidefinite programming relaxations of maximum \(k\)-section, ILP-Based Local Search for Graph Partitioning, An exact algorithm for graph partitioning, The State-of-the-Art in Conic Optimization Software, SCIP: solving constraint integer programs, An exact combinatorial algorithm for minimum graph bisection, A bounded-error quantum polynomial-time algorithm for two graph bisection problems, Unnamed Item, Engineering Branch-and-Cut Algorithms for the Equicut Problem

Uses Software

• SCIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The analysis of a nested dissection algorithm
• Min-cut clustering
• Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
• On the \(0/1\) knapsack polytope
• A spectral bundle method with bounds
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Some new classes of facets for the equicut polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• On the Graph Bisection Cut Polytope
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Bundle Method for Semidefinite Programming
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Geometry of cuts and metrics