Lifting and separation procedures for the cut polytope
DOI10.1007/S10107-013-0688-2zbMATH Open1297.90133OpenAlexW1973648690WikidataQ58002879 ScholiaQ58002879MaRDI QIDQ403653FDOQ403653
Authors: Thorsten Bonato, Michael Jünger, Gerhard Reinelt, G. Rinaldi 
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
- The traveling salesman problem. A computational study.
- 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 (21)
- A new separation algorithm for the Boolean quadric and cut polytopes
- Generalized cut and metric polytopes of graphs and simplicial complexes
- Target cuts from relaxed decision diagrams
- Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
- Local search inequalities
- General cut-generating procedures for the stable set polytope
- 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
- Necessary conditions for extended noncontextuality in general sets of random variables
- A polyhedral study of lifted multicuts
- Quantum annealing versus digital computing. An experimental comparison
- 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
- The Boolean quadric polytope
- Coordinated cutting plane generation via multi-objective separation
- 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)
