Título
[en] AN IMPROVED EXACT METHOD FOR THE UBQP
Título
[pt] UM MÉTODO EXATO MELHORADO PARA O UBQP
Autor
[pt] DANIEL FLEISCHMAN
Vocabulário
[pt] SEMIDEFINITE PROGRAMMING
Vocabulário
[pt] UNCONSTRAINED BINARY QUADRATIC PROGRAMMING
Vocabulário
[pt] BRANCH-AND-BOUND
Resumo
[pt] A Programação Quadrática Binária Irrestrita (UBQP) é amplamente
estudada. Trata-se de uma ferramenta de modelagem poderosa, mas
otimizar de um problema NP-difícil. Neste trabalho uma nova abordagem
é apresentada, que pode ser usada para construir um algoritmo exato.
Além disso, a ideia básica que fundamenta o trabalho pode ser usado em
um espectro ainda mais amplo de problemas. O algoritmo exato derivado
do novo método é altamente paralelizável, o que é uma característica
desejável nos dias de hoje em que cloud computing já é uma realidade. Para
instâncias razoavelmente grandes do UBQP, o novo método pode paralelizar
a centenas, ou até milhares, de núcleos com facilidade, com um aumento
de desempenho quase linear.
Resumo
[en] Unconstrained Binary Quadratic Programming (UBQP) is widely studied.
It is a powerful modeling tool and its associate problem is NP-hard. In
this work a new approach is introduced, which can be used to build an
exact algorithm. Also, the fundamental idea behind it can be used in an
even wider family of problems. This exact algorithm derived from the new
method is highly parallelizable, which is a desired feature nowadays, when
the cloud computing is a reality. For reasonably large instances of UBQP,
the new method can parallelize to hundreds, or even thousands, of cores
easily, with a near-linear speedup.
Orientador(es)
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
ALEXANDRE STREET DE AGUIAR
Banca
NELSON MACULAN FILHO
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Catalogação
2011-03-11
Apresentação
2010-08-04
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=17054@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=17054@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.17054
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT E SUMÁRIO PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF CAPÍTULO 6 PDF CAPÍTULO 7 PDF CAPÍTULO 8 PDF REFERÊNCIAS BIBLIOGRÁFICAS PDF