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
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Portuguese |
| Published: |
Universidade Federal de São Carlos
2009-12-01
|
| Series: | Gestão & Produção |
| Subjects: | |
| Online Access: | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0104-530X2009000400002 |
| _version_ | 1819195684835819520 |
|---|---|
| author | Geraldo Regis Mauri Luiz Antonio Nogueira Lorena |
| author_facet | Geraldo Regis Mauri Luiz Antonio Nogueira Lorena |
| author_sort | Geraldo Regis Mauri |
| collection | DOAJ |
| description | 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.<br>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. |
| first_indexed | 2024-12-23T02:16:41Z |
| format | Article |
| id | doaj.art-b103f94daebc4f99a000a94dcea5040b |
| institution | Directory Open Access Journal |
| issn | 0104-530X 1806-9649 |
| language | Portuguese |
| last_indexed | 2024-12-23T02:16:41Z |
| publishDate | 2009-12-01 |
| publisher | Universidade Federal de São Carlos |
| record_format | Article |
| series | Gestão & Produção |
| spelling | doaj.art-b103f94daebc4f99a000a94dcea5040b2022-12-21T18:03:39ZporUniversidade Federal de São CarlosGestão & Produção0104-530X1806-96492009-12-0116451552510.1590/S0104-530X2009000400002Geraçã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 problemGeraldo Regis MauriLuiz Antonio Nogueira LorenaEste 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.<br>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.http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0104-530X2009000400002Programação quadráticaGeração de colunasRelaxação lagrangeanaQuadratic programmingColumn generationLagrangean relaxation |
| spellingShingle | Geraldo Regis Mauri Luiz Antonio Nogueira Lorena 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 Gestão & Produção Programação quadrática Geração de colunas Relaxação lagrangeana Quadratic programming Column generation Lagrangean relaxation |
| title | 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 |
| title_full | 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 |
| title_fullStr | 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 |
| title_full_unstemmed | 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 |
| title_short | 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 |
| title_sort | geracao de colunas com divisao em clusters para o problema de programacao quadratica binaria irrestrita column generation with clusters for the unconstrained binary quadratic programming problem |
| topic | Programação quadrática Geração de colunas Relaxação lagrangeana Quadratic programming Column generation Lagrangean relaxation |
| url | http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0104-530X2009000400002 |
| work_keys_str_mv | AT geraldoregismauri geracaodecolunascomdivisaoemclustersparaoproblemadeprogramacaoquadraticabinariairrestritacolumngenerationwithclustersfortheunconstrainedbinaryquadraticprogrammingproblem AT luizantonionogueiralorena geracaodecolunascomdivisaoemclustersparaoproblemadeprogramacaoquadraticabinariairrestritacolumngenerationwithclustersfortheunconstrainedbinaryquadraticprogrammingproblem |