Applications of Semidefinite Programming in Combinatorial Optimization

• Grant number: 13/20740-9
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: January 01, 2014
• End date: August 31, 2014
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Marcel Kenji de Carli Silva
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM

Abstract

In this project we focus on the development of tools from Semidefinite Programming and Convex Analysis for applications in Combinatorial Optimization, aiming to generalize the approach from Polyhedral Combinatorics. We are interested on the facial structure of semidefinite relaxations for certain combinatorial problems and its correspondence with combinatorial properties of the problems at hand. As a byproduct, we hope to enhance our understanding about the real gain of semidefinite formulations that make them so tighter than linear formulations for certain problems, and potentially replicate this success in other problems.Most of the known results in this line of research revolves around the central object known as the theta body of a graph, from which one may define the Lovász theta function. The theory surrounding these objects is quite rich and elegant, and it also applies to the semidefinite program utilized by Goemans and Williamson in their famous approximation algorithm for the maximum cut problem. We describe certain research directions involving the facial structure of these objects and the corresponding optimality conditions, as well as broader avenues of research with the goal of determining the true power of semidefinite formulations in Combinatorial Optimization and otherwise.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

DE CARLI SILVA, MARCEL K.; TUNCEL, LEVENT. VERTICES OF SPECTRAHEDRA ARISING FROM THE ELLIPTOPE, THE THETA BODY, AND THEIR RELATIVES. SIAM JOURNAL ON OPTIMIZATION, v. 25, n. 1, p. 295-316, 2015. (13/20740-9)

DE CARLI SILVA, MARCEL K.; TUNCEL, LEVENT. An axiomatic duality framework for the theta body and related convex corners. MATHEMATICAL PROGRAMMING, v. 162, n. 1-2, p. 283-323, MAR 2017. (13/20740-9, 13/03447-6)