Engineering branch-and-cut algorithms for the equicut problem

DOI10.1007/978-3-319-00200-2_2MaRDI QIDQ2848989zbMATH OpenOpenAlexFDO

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

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

bisectionbranch-and-cutequicutgraph partitioninglinear programmingmaximum-cutsemidefinite programming

Mathematics Subject Classification ID

Linear programming (90C05) Semidefinite programming (90C22) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A branch-and-cut algorithm for the equicut problem
• Solution of large weighted equicut problems
• Some new classes of facets for the equicut polytope
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• scientific article; zbMATH DE number 1054945

Cites work

• A branch-and-cut algorithm for the equicut problem
• A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An Efficient Heuristic Procedure for Partitioning Graphs
• An efficient semidefinite programming relaxation for the graph partition problem
• Cardinality constrained Boolean quadratic polytope
• CSDP, A C library for semidefinite programming
• Engineering branch-and-cut algorithms for the equicut problem
• Facets of the Bipartite Subgraph Polytope
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 1182569 (Why is no real title available?)
• scientific article; zbMATH DE number 2084783 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
• Integer Programming and Combinatorial Optimization
• Local cuts revisited
• LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison
• Min-cut clustering
• On semidefinite programming relaxations of maximum \(k\)-section
• Solving Graph Bisection Problems with Semidefinite Programming
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Some new classes of facets for the equicut polytope
• The cut polytope and the Boolean quadric polytope
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• The node capacitated graph partitioning problem: A computational study

Cited in

(7)

• A branch-and-cut algorithm for the equicut problem
• Solution of large weighted equicut problems
• An overview of graph covering and partitioning
• Engineering branch-and-cut algorithms for the equicut problem
• scientific article; zbMATH DE number 1054945 (Why is no real title available?)
• scientific article; zbMATH DE number 1775539 (Why is no real title available?)
• Target cuts from relaxed decision diagrams

Describes a project that uses

Uses Software

• CSDP
• CPLEX
• Biq Mac

This page was built for publication: Engineering branch-and-cut algorithms for the equicut problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2848989)