Algoritmo numérico para solução da programação mista não-linear e inteira

Abstract

O presente trabalho apresenta a formulação e implementação de um algoritmo para a solução de problemas convexos de programação mista não-linear e inteira (MINLP). O algoritmo proposto não segue a tradicional solução seqüencial de subproblemas de programação não-linear (NLP) e problemas mestres de programação mista linear e inteira (MILP). Em vez disso, o problema mestre é definido dinamicamente durante a busca em árvore para reduzir o número de nós que necessitamos ser enumerados. Uma busca em árvore, tipo “branch” e “bound”, é conduzida para determinar limites inferiores das soluções dos subproblemas de programação linear (LP) até encontrar soluções inteiras viáveis. Para estes nós, subproblemas de programação não-linear são resolvidos determinando limites superiores e novas aproximações lineares, as quais são usadas para estender a representação linear dos nós abertos na árvore de busca. Resultados numéricos em alguns problemas testes são relatados, comparando a eficiência do algoritmo com resultados da literatura estudada. Faz-se também uma análise do comportamento frente a problemas testes não-convexos. Palavras-Chave: Otimização, programação mista não-linear e inteira