Decomposi??es Lagrangeanas para o problema de programa??o quadrática binária irrestrita

摘要

O Problema de Programa??o Quadrática Binária Irrestrita - PQ é um dos problemas clássicos na área de otimiza??o n?o-linear cujo objetivo é otimizar uma fun??o quadrática através da escolha de valores binários apropriados para as variáveis de decis?o. Este trabalho prop?e novas alternativas de decomposi??o Lagrangeana para obten??o de limitantes para o PQ. Os métodos propostos tratam uma vers?o linear inteira mista (PQL) do PQ que tem restri??es representadas através de um grafo. Esse grafo é particionado em clusters de vértices formando um problema dual cuja solu??o é dada por um algoritmo de subgradiente. A cada itera??o desse método, os subproblemas formados pelos subgrafos gerados s?o resolvidos pelo CPLEX. Experimentos computacionais tratam um conjunto de dados formado por diversas instancias de difícil solu??o e diferentes características. Os resultados mostram a eficiência dos métodos propostos em rela??o a métodos tradicionais de relaxa??o Lagrangeana e outros métodos encontrados na literatura.