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

Authors

  • Danilo Elias Oliveira
  • Henry Wolkowicz
  • Yangyang Xu

DOI:

https://doi.org/10.5540/03.2017.005.01.0477

Keywords:

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

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.

Downloads

Download data is not yet available.

Published

2017-04-14

Issue

Section

Trabalhos Completos - Otimização