Título: UM MÉTODO EXATO MELHORADO PARA O UBQP
Catalogação: 11/03/2011 Idioma(s): INGLÊS - ESTADOS UNIDOS
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.