Algoritmos para Programação Não Linear Inteira Mista

Informações:

Publicações do PESC

Título
Algoritmos para Programação Não Linear Inteira Mista
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
28/2/2012
Resumo
Neste trabalho, discutimos os principais algoritmos da atualidade para a resolução de problemas de Programação Não Linear Inteira Mista (PNLIM) convexos, abrangendo algoritmos das classes de aproximação linear, branch-and-bound, híbridos e heurísticas. Propomos ainda duas novas abordagens para PNLIM: uma aplicação do algoritmo de particionamento local (local branching), proposto originalmente para o caso linear, e uma nova metodologia híbrida que mistura os algoritmos de aproximação externa e de branch-and-bound padrão. Finalmente, este trabalho tem como último objetivo a apresentação de um novo pacote computacional aberto para PNLIM, o solver Muriqui, que tem por missão agregar todo o conteúdo gerado por este e por futuros estudos. Resultados computacionais sobre um conjunto padrão de problemas de teste são fornecidos.
Abstract
In this work, we discuss the current main algorithms for solving convex Mixed Integer NonLinear Programming problems (MINLP), covering algorithms from several classes: linear approximation, branch-and-bound, hybrid and heuristics. We propose further two new approaches for MINLP: a application of local branching algorithm, originally proposed to linear case, and a new hybrid algorithm that mixes outer approximation and standard branch-and-bound algorithms. Finally, this work has like last objective the presentation of a new open computational package for MINLP, called Muriqui solver, which has the mission of aggregating all contents generated by that and future studies. Computational results on a standard set of test problems are showed.
Arquivo
Topo