Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
type: Item
instance of: scholarly article
title: Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results
zbMATH Open document ID: 1471.90158
author: Viet Hung Nguyen
author: Michel Minoux
published in: Optimization Letters
publication date: 2021-07-08T00:00:00Z
full work available at URL: template rev3.pdf
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C11
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 7369544
zbMATH Keywords: max-cut
zbMATH Keywords: cycle inequalities
zbMATH Keywords: triangle inequalities
zbMATH Keywords: semi-metric polytope
describes a project that uses: OR-Library
describes a project that uses: Biq Mac
describes a project that uses: BiqMac
describes a project that uses: Rudy
MaRDI profile type: Publication
OpenAlex ID: W3109062912
cites work: On cuts and matchings in planar graphs
cites work: On the cut polytope
cites work: The volume algorithm: Producing primal solutions with a subgradient method
cites work: Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
cites work: Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
cites work: Q3094163
cites work: Lifting and separation procedures for the cut polytope
cites work: The cut polytope and the Boolean quadric polytope
cites work: New approaches for optimizing over the semimetric polytope
cites work: Some Network Flow Problems Solved with Pseudo-Boolean Programming
cites work: Q5465120
cites work: Improved semidefinite bounding procedure for solving max-cut problems to optimality
cites work: Q4668573
cites work: Reduced‐size formulations for metric and cut polyhedra in sparse graphs
cites work: Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
DOI: 10.1007/S11590-020-01667-Z
Recommended article: Linear-Time Approximation Algorithms for the Max Cut Problem
Recommended article: Integer Linear Programs and Local Search for Max-Cut
Recommended article: Approximation and intractability results for the maximum cut problem and its variants
Recommended article: New bounds for the maximum cut problem
Recommended article: Q2934582
Recommended article: A novel formulation of the max-cut problem and related algorithm
Recommended article: The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
Recommended article: Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
Recommended article: An optimality cut for mixed integer linear programs
Recommended article: Stronger linear programming relaxations of max-cut
description: scientific article; zbMATH DE number 7369544