A MAX-CUT formulation of 0/1 programs

DOI10.1016/j.orl.2015.12.014zbMath1408.90222arXiv1505.06840OpenAlexW376676247MaRDI QIDQ1785732

Jean-Bernard Lasserre

Publication date: 1 October 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.06840

zbMATH Keywords

linear and quadratic 0/1 programsLP- and semidefinite relaxationsMAX-CUT problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Quadratic programming (90C20)

Related Items

BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints, Mathematical Programming Models and Exact Algorithms, \texttt{EXPEDIS}: an exact penalty method over discrete sets, A new global algorithm for max-cut problem with chordal sparsity, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B, BiqBin: Moving Boundaries for NP-hard Problems by HPC, Bounds for Random Binary Quadratic Programs, \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM, A multilevel analysis of the Lasserre hierarchy, Gaussian mean field lattice gas, Sum-of-squares hierarchies for binary polynomial optimization, Sum-of-squares hierarchies for binary polynomial optimization, Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Uses Software

• GloptiPoly
• Mosek

Cites Work

• Unnamed Item
• Unnamed Item
• Copositive optimization -- recent developments and applications
• Handelman's hierarchy for the maximum stable set problem
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Copositive Programming
• Computational Approaches to Max-Cut
• An Introduction to Polynomial and Semi-Algebraic Optimization
• GloptiPoly 3: moments, optimization and semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Optimisation globale et théorie des moments
• Error Estimates in the Optimization of Degree Two Polynomials on a Discrete Hypercube
• Semidefinite relaxations for partitioning, assignment and ordering problems