AN IMPROVED EXACT METHOD FOR THE UBQP / UM MÉTODO EXATO MELHORADO PARA O UBQP

AUTOR(ES)

DANIEL FLEISCHMAN

DATA DE PUBLICAÇÃO

2010

RESUMO

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.

ASSUNTO(S)

semidefinite programming branch-and-bound unconstrained binary quadratic programming

Documentos Relacionados

• Um algoritmo exato para problemas das P-medianas
• Um algoritmo exato para um problema de Galeria de Arte
• Um algoritmo exato para a otimização de carteiras de investimento com restrições de cardinalidade
• Um algoritmo exato para o problema de empacotamento bidimensional em faixas
• Um algoritmo exato para o problema da mochila