Autores

4582
47,603,752
4583
47,603,752
4584
47,603,752

Informações:

Publicações do PESC

Título
Um Algoritmo Utilizando Programação Semidefinida para o Problema de Dois Níveis Linear
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
29/9/2006
Resumo

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.

Abstract

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.

Arquivo
Topo