  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.
