A NOTION OF TOTAL DUAL INTEGRALITY FOR CONVEX, SEMIDEFINITE, AND EXTENDED FORMULATIONS

Autor(es)

de Carli Silva, Marcel K. ^[1] ; Tuncel, Levent ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil

^[2] Univ Waterloo, Fac Math, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1 - Canada

• Tipo de documento: Artigo Científico
• Fonte: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 34, n. 1, p. 470-496, 2020.
• Citações Web of Science: 0

Resumo

Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming strong duality into combinatorial min-max theorems. The definition of a linear inequality system being totally dual integral (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 linear program (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 rank-one 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 primal-dual 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 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. (AU)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático