Gestão & Produção (Dec 2009)
Geração de colunas com divisão em clusters para o problema de programação quadrática binária irrestrita Column generation with clusters for the unconstrained binary quadratic programming problem
Abstract
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.This paper proposes a new alternative of column generation (GC) based on the lagrangean relaxation with clusters (LagClus) to solve the Unconstrained Binary Quadratic Programming Problem (PQ). The PQ is a classical non-linear problem of optimizing a quadratic function by suitable choices of binary decisions variables. The proposed GC treats a mixed binary linear model (PQL) of PQ with constraints represented by a graph and divided through a partitioning heuristic. Besides finding feasible solutions the proposed method still presents two alternative ways to find bounds for PQ. Several computational experiments were performed using hard instances with different features. GC is compared to traditional lagrangean relaxation and other methods recently proposed presenting improved results for most of these instances.
Keywords
