[en] ALGORITHM RELAX-AND-CUT FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM

Detalhes bibliográficos
Ano de defesa: 2005
Autor(a) principal: MARCIO DE MORAES PALMEIRA
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: por
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:
Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=7404&idi=1
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=7404&idi=2
http://doi.org/10.17771/PUCRio.acad.7404
Resumo: [pt] Consideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima.