Lifting and separation procedures for the cut polytope

DOI10.1007/s10107-013-0688-2zbMath1297.90133OpenAlexW1973648690WikidataQ58002879 ScholiaQ58002879MaRDI QIDQ403653

Michael Jünger, Gerhard Reinelt, Giovanni Rinaldi, Thorsten Bonato

Publication date: 29 August 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: http://e-archive.informatik.uni-koeln.de/674/8/mc_V9.pdf

zbMATH Keywords

cut polytopebranch-and-cutmax-cut problemseparation algorithmIsing spin Glass modelunconstrained Boolean quadratic programming

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Combinatorial optimization (90C27) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Boolean programming (90C09)

Related Items

The Boolean Quadric Polytope, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Generalized cut and metric polytopes of graphs and simplicial complexes, Necessary conditions for extended noncontextuality in general sets of random variables, Generalised 2-circulant inequalities for the max-cut problem, A note on the 2-circulant inequalities for the MAX-cut problem, Retracts and algebraic properties of cut algebras, Quantum Annealing versus Digital Computing, Faster exact solution of sparse maxcut and QUBO problems, Target Cuts from Relaxed Decision Diagrams, Seminormality, canonical modules, and regularity of cut polytopes, The hypermetric cone and polytope on eight vertices and some generalizations, Local search inequalities, Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, Efficient semidefinite branch-and-cut for MAP-MRF inference, A new separation algorithm for the Boolean quadric and cut polytopes

Uses Software

• ABACUS
• Concorde
• Biq Mac
• BiqMac
• Rudy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Handbook on semidefinite, conic and polynomial optimization
• On cuts and matchings in planar graphs
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Lifting facets of the cut polytope
• Local cuts revisited
• Separating subdivision of bicycle wheel inequalities over cut polytopes
• One-third-integrality in the max-cut problem
• Exact ground states of two-dimensional \(\pm J\) Ising spin glasses
• New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities
• Generating facets for the cut polytope of a graph by triangular elimination
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Semidefinite Relaxations for Integer Programming
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
• An Interior-Point Method for Semidefinite Programming
• A Convenient Method for Generating Normal Variables
• Two-party Bell inequalities derived from combinatorics via triangular elimination
• Geometry of cuts and metrics