Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B

DOI10.1007/S11590-022-01944-ZMaRDI QIDQ6155645zbMATH OpenOpenAlexFDO

Authors Timotej Hrga, Janez Povh

Publication date 5 June 2023

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-022-01944-z

zbMATH Keywords

semidefinite programmingaugmented Lagrangian methodcutting-plane methodmax-cut problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Semidefinite programming (90C22)

Recommendations

• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Strengthened semidefinite programming relaxations for the max-cut problem.
• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2159019 (Why is no real title available?)
• A Limited Memory Algorithm for Bound Constrained Optimization
• A MAX-CUT formulation of 0/1 programs
• A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
• An Interior-Point Method for Semidefinite Programming
• Applications of cut polyhedra. II
• BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
• Computational approaches to MAX-cut
• Computing a nearest symmetric positive semidefinite matrix
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Quantum annealing versus digital computing. An experimental comparison
• Reducibility among combinatorial problems
• Regularization methods for semidefinite programming
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• \texttt{EXPEDIS}: an exact penalty method over discrete sets
• \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM

Cited in

(3)

• Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
• scientific article; zbMATH DE number 5209784 (Why is no real title available?)

This page was built for publication: Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B

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