Um Algoritmo Utilizando Programação Semidefinida para o Problema de Dois Níveis Linear
Autores
4582 |
47,603,752
|
|
4583 |
47,603,752
|
|
4584 |
47,603,752
|
Informações:
Publicações do PESC
A programação em dois níveis atualmente é uma das áreas que vem merecendo uma grande atenção por apresentar uma estrutura hierárquica, a qual é caracterizada pela presença de dois problemas. Neste trabalho, será apresentado um estudo sobre o problema de dois níveis, de uma maneira geral, e mais especificamente do problema de dois níveis linear. Algumas formulações e condições de otimalidade para o problema serão apresentadas assim como alguns dos principais algoritmos encontrados na literatura para resolver o problema de dois níveis linear.
Será apresentado um estudo do método de branch-and-bound baseado no trabalho de Bard e Moore para resolver o problema de dois níveis linear e, baseado nesse trabalho, será proposta uma relaxação semidefinida positiva, buscando assim obter melhores limites que serão utilizados no algoritmo de branch-and-bound para resolver o problema de dois níveis linear. Serão apresentados resultados computacionais e estes resultados serão comparados com os de Bard e Moore.
Nowadays, bilevel programming problem is a field of great interested because it has a hierarchical structure, which has two problems.
In this work we study bilevel programming in a general way, and more specifically linear bilevel programming. We present some formulations and some optimality conditions for linear cases as well as comment some algorithms found in literature.
We study a branch-and-bound method based on the work of Bard and Moore and also propose a semidefinite relaxation to gain better limits for linear bilevel programming. We use this limits in the branch-and-bound algorithm and present numerical results comparing both algorithms.