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

Autor(es)

Geraldo Regis Mauri ^[1] ; Luiz Antonio Nogueira Lorena ^[2]

Afiliação do(s) autor(es)

^[1] Universidade Federal do Espírito Santo. Departamento de Engenharia Rural. Centro de Ciências Agrárias - Brasil

^[2] Instituto Nacional de Pesquisas Espaciais. Laboratório Associado de Computação e Matemática Aplicada - Brasil

• Tipo de documento: Artigo Científico
• Fonte: Gestão & Produção; v. 16, n. 4, p. 515-525, 2009-12-00.

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. (AU)

• Processo FAPESP: 04/11053-9 - Metodologia híbrida para resolução do problema dial-a-ride
• Beneficiário: Geraldo Regis Mauri
• Modalidade de apoio: Bolsas no Brasil - Doutorado