Papers › Dealing with inequality constraints in large-scale semidefinite relaxations for graph...
Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems
Federico Battista, Marianna De Santis
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical in terms of both computational time and memory requirements. Certain first-order methods, such as Alternating Direction Methods of Multipliers (ADMMs), established as suitable algorithms to deal with large-scale SDPs and gained growing attention over the past decade. In this paper, we focus on an ADMM designed for SDPs in standard form and extend it to deal with inequalities when solving SDPs in general form. Beside numerical results on randomly generated instances, where we show that our method compares favorably with respect to the state-of-the-art solver SDPNAL+, we present results on instances from SDP relaxations of classical combinatorial problems such as the graph coloring problem and the maximum clique problem. Through extensive numerical experiments, we show that even an inaccurate dual solution, obtained at a generic iteration of our proposed ADMM, can represent an efficiently recovered valid bound on the optimal solution of the combinatorial problems considered, as long as an appropriate post-processing procedure is applied.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections