Um Algoritmo Utilizando Programação Semidefinida para o Problema de Dois Níveis Linear

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.