Dealing with inequality constraints in large scale semidefinite relaxations for graph coloring and maximum clique problems

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 both in terms of computational time and memory requirements. First order methods, such as Alternating Direction Methods of Multipliers (ADMMs), turned out to be suitable algorithms to deal with large scale SDPs and gained growing attention during 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. This allows to handle SDP relaxations of classical combinatorial problems such as the graph coloring problem and the maximum clique problem, that we consider in our extensive numerical experience. The numerical results show the comparison of the method proposed equipped with a post-processing procedure with the state-of-the-art solver SDPNAL+.

Article

Download

View Dealing with inequality constraints in large scale semidefinite relaxations for graph coloring and maximum clique problems