  


A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations
Marcel de Carli Silva(marcel.csilvagmail.com) Abstract: Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric minmax relations given by linear programming Strong Duality into combinatorial minmax theorems. The definition of total dual integrality (TDI) revolves around the existence of optimal dual solutions that are integral, and thus naturally applies to a host of combinatorial optimization problems that are cast as integer programs whose LP relaxations have the TDIness property. However, when combinatorial problems are formulated using more general convex relaxations, such as semidefinite programs (SDPs), it is not at all clear what an appropriate notion of integrality in the dual program is, thus inhibiting the generalization of the theory to more general forms of structured convex optimization. (In fact, we argue that the rankone constraint usually added to SDP relaxations is not adequate in the dual SDP.) In this paper, we propose a notion of total dual integrality for SDPs that generalizes the notion for LPs, by relying on an "integrality constraint" for SDPs that is primaldual symmetric. A key ingredient for the theory is a generalization to compact convex sets of a result of Hoffman for polytopes, fundamental for generalizing the polyhedral notion of total dual integrality introduced by Edmonds and Giles. We study the corresponding theory applied to SDP formulations for stable sets in graphs using the Lov\'asz 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. Keywords: total dual integrality, semidefinite programming, Lovász theta function Category 1: Combinatorial Optimization Category 2: Linear, Cone and Semidefinite Programming Category 3: Integer Programming Citation: arXiv:1801.09155, January 2018 Download: [PDF] Entry Submitted: 01/30/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  