Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization

DOI10.1287/ijoc.2020.1008OpenAlexW3132970834MaRDI QIDQ5084606

Sven Mallach, Michael Jünger

Publication date: 28 June 2022

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2020.1008

zbMATH Keywords

maximum cutinteger linear programmingbinary quadratic optimization

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items

Faster exact solution of sparse maxcut and QUBO problems, A new global algorithm for max-cut problem with chordal sparsity, Optimal design of line replaceable units

Cites Work

• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Weakly bipartite graphs and the max-cut problem
• Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
• The cut polytope and the Boolean quadric polytope
• Exact ground states of two-dimensional \(\pm J\) Ising spin glasses
• A new separation algorithm for the Boolean quadric and cut polytopes
• Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• On the cut polytope
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Unnamed Item
• Unnamed Item