[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. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP),
which consists of maximizing a quadratic Boolean function
subject to a linear capacity constraint. The problem has
applications in several areas such as telecommunications,
financial engineering, location problems, graph theory
(Max Clique).
We propose a Branch-and-Bound algorithm to solve
the QKP to optimality based on lagrangian Relaxation.
Initially, we linearize the formulation of the problem
given above and then we relax-and-cut dinamicaly its
continous relaxation using a few classes of valid
inequalities. In the process the Subgradient Method is
applied.
We also propose a new primal heuristic for the QKP
that has improved upon previous approaches, and finds an
optimal solution for all of the instances we considered.
The good quality of our upper and lower bounds is
translated into small gaps at the root node of the
enumeration tree (usually below 1%, even for difficult
instances). That, coupled with tests for fixing variables,
allowed optimality to be proven within only a few nodes of
the enumeration tree.
We provide a way to randomly generate instances
of the QKP harder than those in the literature. We report
computational results for randomly generated instances
(the ones in the literature and the new harder ones) of
QKP with different densities and sizes; and also for Known
instances of Max Clique problems.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:7404 |
| Date | 01 November 2005 |
| Creators | MARCIO DE MORAES PALMEIRA |
| Contributors | OSCAR PORTO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0028 seconds