Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Mathematical Programming

Improved semidefinite bounding procedure for solving Max-Cut problems to optimality

Nathan Krislock, Jérôme Malick, Frédéric Roupin

Published Oct 13, 2012• 57 citations
Publisher
DOI
10.1007/s10107-012-0594-z

Related papers

Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations

Franz Rendl, Giovanni Rinaldi, Angelika Wiegele

Mathematical Programming•Jul 21, 2008•7 citations

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

Dachuan Xu, Shu-zhong Zhang

Science in China Series A Mathematics•Jul 30, 2007•7 citations

A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations

Franz Rendl, Giovanni Rinaldi, Angelika Wiegele

Springer eBooks•Jun 25, 2007•55 citations

A Coherent Ising Machine for MAX-CUT Problems: Performance Evaluation against Semidefinite Programming and Simulated Annealing

Yoshitaka Haribara, Shoko Utsunomiya, Y. Yamamoto

arXiv:1501.07030•Lecture notes in physics•Dec 29, 2015•66 citations

BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving Binary Quadratic Problems

Nathan Krislock, Jérôme Malick, Frédéric Roupin

This article presents BiqCrunch , an exact solver for binary quadratic optimization problems. BiqCrunch is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max- k -Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.

ACM Transactions on Mathematical Software•Jan 2, 2017•57 citations

Semidefinite programming approaches for stable set and max-cut problems

Lennart Sinjorgo

This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.

•Jan 20, 2026•0 citations
This thesis investigates the use of semidefinite programming (SDP) for solving (variants of) the well-known stable set and max-cut problems. Chapter 2 considers a generalization of the stable set problem, and a corresponding SDP relaxation. Similarly, Chapter 3 considers a generalization of the max-cut problem that involves complex roots of unity. Various complex SDP relaxations of this generalized max-cut problem are studied. Chapter 4 provides approximation algorithms for the quantum generalization of the max-cut problem. These approximation algorithms employ a hierarchy of SDP relaxations for noncommutative polynomial optimization problems. Chapter 5 provides an SDP algorithm for computing bounds on the stability numbers of graphs. Chapter 6 provides an SDP algorithm for solving the MAX-SAT problem. Chapters 5 and 6 provide extensive numerical results on these algorithms.