Aggregated quadratic formulations and semidefinite relaxations of the stable set polytope

The stable set problem admits various binary linear and quadratic formulations. The Shor relaxation of a particular quadratic formulation is the well-known theta body. We consider aggregations of quadratic constraints of this formulation, yielding exact and inexact quadratic formulations of the stable set problem, and then establish conditions under which the aggregated quadratic formulation is exact. By applying the Shor relaxation to aggregated quadratic formulations, we obtain new families of semidefinite relaxations of the stable set polytope. Conditions are established for the well-known clique inequalities to remain valid for these relaxations. We also compare the SDP-based aggregation closures of such relaxations and establish the surprising result that exact aggregations do not necessarily yield stronger closures than their inexact counterparts. In particular, one of our aggregation closures equals the theta body, whereas the other one can be strictly weaker.

Article

Download

View PDF