Return to Colloquia & Seminar listing
Total Dual Integrality for Convex, Semidefinite and Extended Formulations
Mathematics of Data & Decisions| Speaker: | Levent Tunçel, U Waterloo |
| Related Webpage: | http://www.math.uwaterloo.ca/~ltuncel/ |
| Location: | 1147 MSB |
| Start time: | Tue, Apr 9 2019, 4:10PM |
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). Our notion generalizes the existing notion for Linear Programming problems (LPs), by relying on 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, fundamental for generalizing the polyhedral notion of total dual integrality introduced by Edmonds and Giles in the 1970's. We study the corresponding theory applied to 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. We also relate dual integrality of an SDP formulation for the maximum cut problem to bipartite graphs. Total dual integrality for extended formulations naturally comes into play in this context.
Based on joint work with Marcel de Carli Silva.