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

AUTOR(ES)

Mauri, Geraldo Regis, Lorena, Luiz Antonio Nogueira

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2009-04

RESUMO

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.

ASSUNTO(S)

programação quadrática decomposição lagrangeana limitantes

Documentos Relacionados

• Geração de colunas com divisão em clusters para o problema de programação quadrática binária irrestrita
• Evolução diferencial híbrida com programação quadrática aplicada ao problema de despacho econômico de energia elétrica
• Modelo de programação quadrática para análise da movimentação logística e comercialização da soja brasileira
• Uma abordagem de programação inteira para o problema da triangulação de custo minimo
• Metodo para resolver um problema de programação linear dinamica