LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison

DOI10.1007/s12532-012-0040-5zbMath1275.90053OpenAlexW2077688031MaRDI QIDQ2392866

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

Publication date: 5 August 2013

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-012-0040-5

zbMATH Keywords

graph bisectionpolyhedral combinatoricssemidefinite programscutting plane algorithmsbranch and cut algorithms

Mathematics Subject Classification ID

Semidefinite programming (90C22) Large-scale problems in mathematical programming (90C06) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items

Improved exact approaches for row layout problems with departments of equal length, Partitioning through projections: strong SDP bounds for large graph partition problems, Cardinality-constrained distributionally robust portfolio optimization, A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, A framework for solving mixed-integer semidefinite programs, The MIN-cut and vertex separator problem, Efficient semidefinite branch-and-cut for MAP-MRF inference, A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems, An exact combinatorial algorithm for minimum graph bisection, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Semidefinite programming and eigenvalue bounds for the graph partition problem

Uses Software

• SCIP
• AMPL
• CPLEX
• METIS
• ConicBundle
• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• The analysis of a nested dissection algorithm
• The node capacitated graph partitioning problem: A computational study
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• 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
• Branching rules revisited
• Some new classes of facets for the equicut polytope
• Dynamic bundle methods
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems
• On Interior-Point Warmstarts for Linear and Combinatorial Optimization
• On the Graph Bisection Cut Polytope
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Bundle Method for Semidefinite Programming
• Computational Experience with an Interior Point Cutting Plane Algorithm
• On the cut polytope
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• Fixing Variables in Semidefinite Relaxations
• Constraint Integer Programming: A New Approach to Integrate CP and MIP
• Geometry of cuts and metrics
• Benchmarking optimization software with performance profiles.