Title: Total Dual Integrality for Convex, Semidefinite and Extended Formulations
| Speaker: | Levent Tuncel |
| Affiliation: | University of Waterloo |
| Zoom: | Please email Emma Watson |
Abstract:
Within the context of characterizations of exactness of convex relaxations of 0,1 integer programming problems, we present a notion of total dual integrality for Semidefinite Optimization Problems (SDPs), convex optimization problems and extended formulations of convex sets.
Our notion generalizes the existing notion for Linear Programming problems. We propose an “integrality constraint” for SDPs that is primal-dual symmetric. A key ingredient for the theory is a generalization to compact convex sets of a theorem of Hoffman for polytopes.
This particular generalization is useful in generalizing the polyhedral notion of total dual integrality introduced by Edmonds and Giles in the 1970’s to SDPs and convex optimization problems. We study the implications of our new theory on SDP formulations for stable sets in graphs using the Lovasz theta function and show that total dual integrality in this case corresponds to the underlying graph being perfect. Total dual integrality for extended formulations of convex sets naturally comes into play in this context.
Based on joint work with Marcel de Carli Silva.