Aplicações de Programação Semidefinida em Otimização Combinatória

• Processo: 13/20740-9
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de janeiro de 2014
• Data de Término da vigência: 31 de agosto de 2014
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Yoshiko Wakabayashi
• Beneficiário: Marcel Kenji de Carli Silva
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM
• Assunto(s): Otimização combinatória Combinatória poliédrica
• Palavra(s)-Chave do Pesquisador: Combinatória Poliédrica | Espectraedro | Função teta de Lovász | Programação semidefinida | Otimização Combinatória

Resumo

O foco deste projeto é o desenvolvimento de ferramentas de Programação Semidefinida e Análise Convexa para aplicação em Otimização Combinatória, visando generalizar a abordagem da Combinatória Poliédrica. Estamos interessados na estrutura facial de relaxações semidefinidas para certos problemas combinatórios e sua correspondência com propriedades combinatórias dos problemas em questão. Como subproduto, esperamos aprofundar nossa compreensão sobre o ganho real de formulações semidefinidas que lhe tornam tão superiores a formulações lineares para certos problemas, e potencialmente replicar esse sucesso para novos problemas.A maioria dos resultados existentes nessa linha de pesquisa envolve o objeto central conhecido como corpo teta de um grafo, a partir do qual se define a função teta de Lovász. A teoria em torno desses objetos é muito rica e elegante, e também se aplica ao programa semidefinido utilizado por Goemans e Williamson em seu famoso algoritmo de aproximação para o problema do corte máximo. Descrevemos algumas direções de pesquisa envolvendo a estrutura facial desses objetos e das respectivas condições de otimalidade, bem como avenidas mais amplas de pesquisa com o objetivo de determinar o real poder de formulações semidefinidas em Otimização Combinatória e em geral.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

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)

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)