232. Aggregated Formulations and Relaxations of the Stable Set Polytope
Invited abstract in session MD-11: Applications of conic optimization, stream Conic Optimization.
Monday, 16:30-18:30Room: B100/5017
Authors (first author is the speaker)
| 1. | Haobang Zhou
|
| The University of Edinburgh | |
| 2. | Akshay Gupte
|
| School of Mathematics, University of Edinburgh | |
| 3. | E. Alper Yildirim
|
| School of Mathematics, The University of Edinburgh |
Abstract
The stable set polytope admits a binary quadratic representation, whose Shor relaxation is the well-known theta body. We consider aggregations of quadratic constraints before and after applying the Shor relaxation, thus yielding new families of semidefinite relaxations. Conditions are established for the well-known valid inequalities for the stable set polytope to remain valid for the aggregations. We also compare the closures of such aggregations and establish the surprising result that aggregations preserving exact formulations do not necessarily yield stronger relaxations than their inexact counterparts. In particular, one of our aggregation closures equals the theta body, whereas the other one equals a relaxation of the theta body obtained by relaxing equalities to inequalities.
This is joint work with Akshay Gupte and Alper Yildirim.
Keywords
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers