Geração de colunas com divisão em clusters para o problema de programação quadrática binária irrestrita

AUTOR(ES)

Mauri, Geraldo Regis, Lorena, Luiz Antonio Nogueira

FONTE

Gestão & Produção

DATA DE PUBLICAÇÃO

2009-12

RESUMO

Este trabalho propõe uma nova alternativa de geração de colunas (GC), baseada na relaxação lagrangeana com divisão em clusters (LagClus), para resolução do Problema de Programação Quadrática Binária Irrestrita (PQ). O PQ é um dos problemas clássicos de otimização não-linear, cujo objetivo é resolver uma função quadrática por meio da escolha de valores binários apropriados para as variáveis de decisão. A GC proposta trata um modelo linear inteiro misto (PQL) do PQ, que tem restrições representadas por meio de um grafo e é dividido através de uma heurística de particionamento. Além de encontrar soluções viáveis, o método proposto ainda apresenta duas formas alternativas para obtenção de limitantes para o PQ. Foram realizados vários experimentos computacionais, utilizando-se instâncias de difícil solução com diferentes características. A GC é comparada a métodos tradicionais de relaxação lagrangeana e outros métodos propostos recentemente, sendo que os resultados apresentados são superiores para a maioria das instâncias consideradas.

ASSUNTO(S)

programação quadrática geração de colunas relaxação lagrangeana

Documentos Relacionados

• Decomposições Lagrangeanas 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
• O problema do corte bidimensional : uma abordagem utilizando o metodo de geração de colunas
• Geração de colunas para o problema de dimensionamento de lotes de produção com limitações de capacidade
• Solução do problema de rejeição de perturbações com regulação linear-quadratica