Semidefinite Approaches for Quadratic Integer Programming

We survey some of the recently developed Semidefinite Programming (SDP) approaches and results for quadratic integer problems. We mainly focus on problems where variables can take one of p values (p=2), and especially on bivalent problems. First, standard SDP relaxations are well known to be strongly linked to the Lagrangian approach. This general framework helps to easily compare such relaxations. Second, new ways of using SDP have been proposed to obtain algorithmsthat are practical. We briefly present several examples and discuss the advantages and drawbacks of these approaches