Decomposições Lagrangeanas para o problema de programação quadrática binária irrestrita

Pesquisa Operacional

Geraldo Regis Mauri²  Luiz Antonio Nogueira Lorena¹ 

[1] ,Instituto Nacional de Pesquisas Espaciais Lab. Associado de Computação e Matemática Aplicada São José dos Campos SP

关键词: programação quadrática;    decomposição Lagrangeana;    limitantes;    quadratic programming;    Lagrangean decomposition;    bounds;   

DOI  :  10.1590/S0101-74382009000100006

来源: SciELO

【 摘 要 】

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 instâncias 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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License