[en] AN IMPROVED EXACT METHOD FOR THE UBQP

Detalhes bibliográficos
Ano de defesa: 2011
Autor(a) principal: DANIEL FLEISCHMAN
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: MAXWELL
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
[pt] SEMIDEFINITE PROGRAMMING
[pt] UNCONSTRAINED BINARY QUADRATIC PROGRAMMING
[pt] BRANCH-AND-BOUND
Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=17054&idi=1
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=17054&idi=2
http://doi.org/10.17771/PUCRio.acad.17054
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.

Registros relacionados