Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Geraldo Regis Mauri ; Luiz Antonio Nogueira Lorena
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: Pesquisa Operacional; v. 29, n. 1, p. -, Abr. 2009.
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. (AU)

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