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

• Ano de defesa: 2005
• Autor(a) principal: MARCIO DE MORAES PALMEIRA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] PROGRAMACAO INTEIRA; [pt] OTIMIZACAO COMBINATORIA; [pt] PROGRAMACAO MATEMATICA; [en] INTER LINEAR PROGRAMMIN; [en] COMBINATORIAL OPTIMIZATION; [en] MATH PROGRAMMING
• 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

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