LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
DOI10.1007/S12532-012-0040-5zbMATH Open1275.90053OpenAlexW2077688031MaRDI QIDQ2392866FDOQ2392866
Authors: Marzena Fügenschuh, Christoph Helmberg, Alexander Martin, 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
Recommendations
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- scientific article; zbMATH DE number 5237020
- Solving Graph Bisection Problems with Semidefinite Programming
- Graph bisection revisited
- Semidefinite programming based algorithms for the sparsest cut problem
polyhedral combinatoricssemidefinite programscutting plane algorithmsgraph bisectionbranch and cut algorithms
Linear programming (90C05) Large-scale problems in mathematical programming (90C06) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Semidefinite programming (90C22) Integer programming (90C10)
Cites Work
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Benchmarking optimization software with performance profiles.
- The analysis of a nested dissection algorithm
- A Spectral Bundle Method for Semidefinite Programming
- A spectral bundle method with bounds
- On the Shannon capacity of a graph
- Branching rules revisited
- On interior-point warmstarts for linear and combinatorial optimization
- Geometry of cuts and metrics
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- On the cut polytope
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Title not available (Why is that?)
- On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems
- The node capacitated graph partitioning problem: A computational study
- Min-cut clustering
- Formulations and valid inequalities of the node capacitated graph partitioning problem
- Constraint Integer Programming: A New Approach to Integrate CP and MIP
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- The equipartition polytope. I: Formulations, dimension and basic facets
- Computational Experience with an Interior Point Cutting Plane Algorithm
- Fixing Variables in Semidefinite Relaxations
- Some new classes of facets for the equicut polytope
- The equipartition polytope. II: Valid inequalities and facets
- On the Graph Bisection Cut Polytope
- Nonpolyhedral Relaxations of Graph-Bisection Problems
- On the \(0/1\) knapsack polytope
- Quadratic \(0/1\) optimization and a decomposition approach for the placement of electronic circuits
- Dynamic bundle methods
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (18)
- A framework for solving mixed-integer semidefinite programs
- A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
- Engineering branch-and-cut algorithms for the equicut problem
- The MIN-cut and vertex separator problem
- An exact combinatorial algorithm for minimum graph bisection
- A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
- Semidefinite programming based algorithms for the sparsest cut problem
- Solving Graph Bisection Problems with Semidefinite Programming
- Improved exact approaches for row layout problems with departments of equal length
- Cardinality-constrained distributionally robust portfolio optimization
- A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
- Efficient semidefinite branch-and-cut for MAP-MRF inference
- Title not available (Why is that?)
- Title not available (Why is that?)
- An efficient semidefinite programming relaxation for the graph partition problem
- Semidefinite programming and eigenvalue bounds for the graph partition problem
- Partitioning through projections: strong SDP bounds for large graph partition problems
- Title not available (Why is that?)
Uses Software
This page was built for publication: LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392866)
