A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations

Preprint English OPEN
Silva, Marcel K. de Carli; Tunçel, Levent;
(2018)
  • Subject: Mathematics - Optimization and Control | Mathematics - Combinatorics
    acm: MathematicsofComputing_DISCRETEMATHEMATICS | TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY

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 tot... View more
  • References (41)
    41 references, page 1 of 5

    [1] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998.

    [2] Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms, http://arxiv.org/abs/ 1404.5236, 2014.

    [3] Aharon Ben-Tal and Arkadi Nemirovski. Lectures on modern convex optimization, http://www2.isye.gatech.edu/ ~nemirovs/Lect_ModConvOpt.pdf, 2013.

    [4] Gábor Braun and Sebastian Pokutta. A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set. Oper. Res. Lett., 42(5):307-310, 2014.

    [5] Samuel Burer. On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program., 120(2, Ser. A):479-495, 2009.

    [6] Marcel K. de Carli Silva. Geometric Ramifications of the Lovász Theta Function and Their Interplay with Duality. PhD thesis, University of Waterloo, 2013.

    [7] Marcel K. de Carli Silva and Levent Tunçel. An axiomatic duality framework for the theta body and related convex corners. Math. Program., 162(1):283-323, 2017.

    [8] P. C. P. Carvalho and L. E. Trotter, Jr. An abstract linear duality model. Math. Oper. Res., 14(4):639-663, 1989.

    [9] D. Dadush, S. S. Dey, and J. P. Vielma. The split closure of a strictly convex body. Oper. Res. Lett., 39(2):121-126, 2011.

    [10] Daniel Dadush, Santanu S. Dey, and Juan Pablo Vielma. On the Chvátal-Gomory closure of a compact convex set. Math. Program., 145(1-2, Ser. A):327-348, 2014.

  • Related Organizations (1)
  • Metrics
Share - Bookmark