Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results

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

zbMATH Keywords

max-cuttriangle inequalitiescycle inequalitiessemi-metric polytope

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Uses Software

• OR-Library
• Biq Mac
• BiqMac
• Rudy

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