Engineering Branch-and-Cut Algorithms for the Equicut Problem

DOI10.1007/978-3-319-00200-2_2zbMath1308.90204MaRDI QIDQ2848989

G. Pardella, Andreas Schmutzer, Miguel F. Anjos, Frauke Liers

Publication date: 13 September 2013

Published in: Discrete Geometry and Optimization (Search for Journal in Brave)

Full work available at URL: https://kups.ub.uni-koeln.de/55028/1/main.pdf

zbMATH Keywords

linear programming; semidefinite programming; graph partitioning; branch-and-cut; bisection; equicut; maximum-cut

Mathematics Subject Classification ID

90C22: Semidefinite programming

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C05: Linear programming

90C27: Combinatorial optimization

Related Items

Target Cuts from Relaxed Decision Diagrams, An overview of graph covering and partitioning, Engineering Branch-and-Cut Algorithms for the Equicut Problem

Uses Software

• CSDP
• CPLEX
• Biq Mac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Local cuts revisited
• The node capacitated graph partitioning problem: A computational study
• Min-cut clustering
• Cardinality constrained Boolean quadratic polytope
• A branch-and-cut algorithm for the equicut problem
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• The cut polytope and the Boolean quadric polytope
• Some new classes of facets for the equicut polytope
• On semidefinite programming relaxations of maximum \(k\)-section
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• Engineering Branch-and-Cut Algorithms for the Equicut Problem
• An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• Facets of the Bipartite Subgraph Polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An Efficient Heuristic Procedure for Partitioning Graphs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Solving Graph Bisection Problems with Semidefinite Programming
• CSDP, A C library for semidefinite programming
• Integer Programming and Combinatorial Optimization
• Geometry of cuts and metrics