AbstractsComputer Science

[en] AN IMPROVED EXACT METHOD FOR THE UBQP

by DANIEL FLEISCHMAN




Institution: Pontifical Catholic University of Rio de Janeiro
Department:
Year: 2011
Keywords: [pt] SEMIDEFINITE PROGRAMMING; [pt] BRANCH-AND-BOUND; [pt] UNCONSTRAINED BINARY QUADRATIC PROGRAMMING
Record ID: 1077644
Full text PDF: http://www.maxwell.lambda.ele.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=17054@1


http://www.maxwell.lambda.ele.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=17054@2


Abstract

[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.