On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem

DOI10.1007/S10898-025-01523-3MaRDI QIDQ6921139zbMATH OpenFDO

Authors Soodeh Habibi, Michal Kočvara, M. Stingl

Publication date 6 October 2025

Published in Journal of Global Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10898-025-01523-3

zbMATH Keywords

binary quadratic optimizationinterior-point methodsLasserre hierarchyMAXCUT problempreconditioned conjugate gradientssemidefinite optimization

Mathematics Subject Classification ID

Preconditioners for iterative methods (65F08) Compliance or weight optimization in solid mechanics (74P05) Linear programming (90C05) Semidefinite programming (90C22) Interior-point methods (90C51)

Cites work

• \texttt{EXPEDIS}: an exact penalty method over discrete sets
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• A dynamic inequality generation scheme for polynomial programming
• Alternating direction augmented Lagrangian methods for semidefinite programming
• An independent benchmarking of SDP and SOCP solvers
• An introduction to polynomial and semi-algebraic optimization
• Binary quadratic optimization problems that are difficult to solve by conic relaxations
• BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
• BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
• CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
• Exact Penalty Functions in Constrained Optimization
• Geometric proofs for convex hull defining formulations
• scientific article; zbMATH DE number 1356716 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Minimizer Extraction in Polynomial Optimization Is Robust
• Moment and Polynomial Optimization
• On Handling Free Variables in Interior-Point Methods for Conic Linear Optimization
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• The Operator \Psi for the Chromatic Number of a Graph
• The unconstrained binary quadratic programming problem: a survey
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity

This page was built for publication: On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6921139)