Algoritmos para o Problema da Mochila Quadrática 0-1
Autores
|
5647 |
2599,519,539
|
|
|
5648 |
2599,519,539
|
|
|
5649 |
2599,519,539
|
Informações:
Publicações do PESC
Nesta tese, apresentamos um algoritmo Relax-and-Cut para geração de limites inferiores e superiores para o problema. Estes limites são comparados, sobre um mesmo conjunto de instâncias teste, com outros limites disponíveis na literatura.
Adicionalmente, propomos um algoritmo Branch-and-Cut, que se baseia numa linearização da formulação clássica do problema, fortalecida com a utilização de algumas famílias de desigualdades válidas. A primeira família está associada com a quadratização da desigualdade da mochila que define o problema. As demais definem facetas do Politopo Booleano Quadrático e do Politopo da Mochila 0-1. Desigualdades dos dois últimos tipos são separadas dinamicamente, à medida que se fazem necessárias. Por sua vez, desigualdades da primeira família são incorporadas à reformulação desde o início. Experimentos computacionais mostram que o algoritmo é uma opção atraente para a resolução exata do problema.
Propomos ainda dois algoritmos adicionais Branch-and-Bound, onde nosso algoritmo Relax-and-Cut é primeiramente aplicado no nó raiz da árvore de enumeração junto com alguns testes de fixação de variáveis. Para um dos algoritmos, em cada nó da árvore de enumeração, desigualdades violadas são anexadas a formulação como planos de cortes, transformando assim esse em um algoritmo Branch-and-Cut baseado em Programação Linear. Para o outro, os limites para cada nó da árvore de enumeração são obtidos diretamente através do nosso algoritmo Relax-and-Cut.
The Quadratic 0-1 Knapsack Problem is a very challenging problem that has attracted considerable attention in the literature over the past three decades.
In this thesis, we present a Relax-and-Cut algorithm for generating lower and upper bounds for the problem. These bounds are compared, over a same set of test instances, with bounds available in literature.
Additionally, we also propose a Branch-and-Cut algorithm which is based on linearizing a classic formulation of the problem, strengthened with the use of some families of valid inequalities. The first family is associated with the quadratization of the knapsack inequality that defines the problem. Additional families used define facets of the Quadratic Boolean Polytope and the 0-1 Knapsack Polytope. Inequalities in the latter two families are dynamically separated, as they become necessary. In turn, inequalities from the former family are incorporated into the formulation from the start. Computational experiments show that the algorithm is an attractive option for exactly solving the problem.
Furthermore, we also propose two additional Branch-and-Bound algorithms where our Relax-and-Cut algorithm is firstly applied at the root node of the enumeration tree, together with some variable fixing tests. For one of the algorithms, at every enumeration tree node, violated inequalities are appended to the formulation as cutting planes, thus turning it a Linear Programming based Branch-and-Cut algorithm. For the other one, bounds for every enumeration tree node are directly obtained through our Relax-and-Cut algorithm.