[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:17054 |
| Date | 11 March 2011 |
| Creators | DANIEL FLEISCHMAN |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0024 seconds