MMDA na resolução da relaxação por Programação Semidefinida do Problema Quadrático de Alocação
DOI:
https://doi.org/10.5540/03.2017.005.01.0477Palabras clave:
Problema quadrático de alocação, relaxação por programação semidefi- nida, método dos multiplicadores com direção alternada.Resumen
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.