MMDA na resolução da relaxação por Programação Semidefinida do Problema Quadrático de Alocação

Abstract

A relaxação por Programação Semidefinida (PSD) já demonstrou ser extrema-
mente útil para muitos problemas difı́ceis da Otimização Discreta. Em especial, para o problema quadrático de alocação (PQA), conhecido por ser um dos problemas mais difı́ceis da classe NP-hard da Otimização Combinatória. Várias são as dificuldades encontradas ao se resolver a relaxação por PSD através dos métodos atuais. Neste trabalho, propomos a utilização do método do multiplicadores com direção alternada (MMDA) para resolver a relaxação por PSD do PQA. Obtemos, assim, iterações mais rápidas; um método rápido para se obter soluções com posto deficiente; e, também, uma forma simples de se adicionar
desigualdades de planos de corte. Em nossos experimentos numéricos, obtivemos resultados mais robustos, eficientes e melhores aproximações para as soluções do PQA.