MMDA na resolução da relaxação por Programação Semidefinida do Problema Quadrático de Alocação
Open Access
- 14 April 2017
- conference paper
- Published by Brazilian Society for Computational and Applied Mathematics (SBMAC) in Proceeding Series of the Brazilian Society of Computational and Applied Mathematics
- Vol. 5 (1)
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.Keywords
This publication has 7 references indexed in Scilit:
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- Bounds for the quadratic assignment problem using the bundle methodMathematical Programming, 2006
- A new bound for the quadratic assignment problem based on convex quadratic programmingMathematical Programming, 2001
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3Optimization Methods and Software, 1999
- Semidefinite Programming Relaxations for the Quadratic Assignment ProblemJournal of Combinatorial Optimization, 1998
- QAPLIB – A Quadratic Assignment Problem LibraryJournal of Global Optimization, 1997
- Assignment Problems and the Location of Economic ActivitiesEconometrica, 1957