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

Danilo Elias Oliveira, Henry Wolkowicz, Yangyang Xu

Resumo


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.


Palavras-chave


Problema quadrático de alocação, relaxação por programação semidefi- nida, método dos multiplicadores com direção alternada.

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2017.005.01.0477

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato