Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
From MaRDI portal
Publication:2039061
DOI10.1007/s11590-020-01667-zzbMath1471.90158OpenAlexW3109062912MaRDI QIDQ2039061
Viet Hung Nguyen, Michel Minoux
Publication date: 8 July 2021
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://hal.uca.fr/hal-03018187/file/template_rev3.pdf
Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lifting and separation procedures for the cut polytope
- On cuts and matchings in planar graphs
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- The volume algorithm: Producing primal solutions with a subgradient method
- The cut polytope and the Boolean quadric polytope
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- New approaches for optimizing over the semimetric polytope
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
- Reduced‐size formulations for metric and cut polyhedra in sparse graphs
- On the cut polytope
- Some Network Flow Problems Solved with Pseudo-Boolean Programming
This page was built for publication: Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
