Lifting and separation procedures for the cut polytope
DOI10.1007/S10107-013-0688-2zbMATH Open1297.90133OpenAlexW1973648690WikidataQ58002879 ScholiaQ58002879MaRDI QIDQ403653FDOQ403653
Michael Jünger, Gerhard Reinelt, G. 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
Recommendations
- Lifting facets of the cut polytope
- A polyhedral study of lifted multicuts
- Cutting a polytope
- scientific article; zbMATH DE number 3885658
- Facets and lifting procedures for the set covering polytope
- Lifting of parallelohedra
- On the cut polytope
- scientific article; zbMATH DE number 742976
- Separation and approximation of polyhedral objects
- scientific article; zbMATH DE number 1629819
branch-and-cutcut polytopeseparation algorithmmax-cut problemIsing spin Glass modelunconstrained Boolean quadratic programming
Quadratic programming (90C20) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Boolean programming (90C09)
Cites Work
- Title not available (Why is that?)
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- An Interior-Point Method for Semidefinite Programming
- Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- On the cut polytope
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Geometry of cuts and metrics
- Title not available (Why is that?)
- Title not available (Why is that?)
- The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
- Handbook on semidefinite, conic and polynomial optimization
- On cuts and matchings in planar graphs
- 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
- Semidefinite Relaxations for Integer Programming
- Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
- Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
- A Convenient Method for Generating Normal Variables
- Two-party Bell inequalities derived from combinatorics via triangular elimination
- Lifting facets of the cut polytope
Cited In (18)
- A new separation algorithm for the Boolean quadric and cut polytopes
- Generalized cut and metric polytopes of graphs and simplicial complexes
- Quantum Annealing versus Digital Computing
- Local search inequalities
- Generalised 2-circulant inequalities for the max-cut problem
- Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
- The Boolean Quadric Polytope
- Necessary conditions for extended noncontextuality in general sets of random variables
- A polyhedral study of lifted multicuts
- Retracts and algebraic properties of cut algebras
- Collapsing and lifting for the cut cone
- Efficient semidefinite branch-and-cut for MAP-MRF inference
- Faster exact solution of sparse maxcut and QUBO problems
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- A note on the 2-circulant inequalities for the MAX-cut problem
- Target Cuts from Relaxed Decision Diagrams
- The hypermetric cone and polytope on eight vertices and some generalizations
- Seminormality, canonical modules, and regularity of cut polytopes
Uses Software
This page was built for publication: Lifting and separation procedures for the cut polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q403653)
