Informações:

Publicações do PESC

Título
Métodos de Branch-And-Bound e Penalidades em Programação Linear em dois Níveis
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
7/6/2002
Resumo

Este trabalho trata do problema de programação linear em dois níveis. Suas características e propriedades básicas são apresentadas, bem como os principais algoritmos existentes na literatura voltados a sua resolução. Um estudo comparativo entre dois algoritmos globais conhecidos na literatura é realizado. O primeiro algoritmo faz uso de um método de penalidade associado a um algoritmo do tipo outer approximation. O segundo algoritmo baseia-se em um método branch-and-bound. Foram propostos neste trabalho os algoritmos de penalidade e branch-and-bound modificados. Os mesmos contornaram as deficiências apresentadas pelos algoritmos originais nos testes realizados. As versões modificadas foram desenvolvidas através da introdução de um método enumerativo, no algoritmo de penalidade original, e de um método de penalidade, no algoritmo branch-and-bound original. Estes novos algoritmos mostram ser bem mais eficientes, do ponto de vista computacional, que os originais.

Abstract

This work deals with the linear bilevel programming problem. Its characteristics, properties and the main global algorithms known in literature are presented. A computational study of two global algorithms is carried aut. The first algorithm uses a penalty method together with an outer approximation procedure. The second one is based on a branch-and- bound approach. In this work penalty and branch-and-bound modified algorithms were proposed. They overcome the trouble presented by the original algorithms which were observed in the computational tests. The modified versions were developed by the introduction of an enumerative method in the original penalty algorithm, and by the inserting of a penalty method in the original branch-and-bound algorithm. The obtained algorithms present a better performance, from the computational point of view, than the original ones.

Arquivo
Topo