Algoritmo numérico para a 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 de programação mista não linear e inteira (MINLP) convexos. 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 necessitam ser enumerados. Uma busca "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 e finalmente a análise de um problema aplicado à rede de trocadores de calor.

The current work shows the formulation and implementation of an algorithm for the solution of convex mixed-integer nonlinear programming (MINLP) problems. The proposed algorithm does not follow the traditional sequence solution of nonlinear programming (NLP) subprobems and master problems of mixed-integer linear programming (MILP). Instead, the master problem is defined dynamically during the tree search to reduce the number of nodes that need to be enumerated. A branch and bound search is performed to predict lower bounds by solving linear programming (LP) subprobems until feasible integer solutions are found. For these nodes nonlinear programming subproblems are solved, providing upper bounds and new linear aproximations which are used to tighten the linear representation of the open nodes in the search tree. Numerical results on some test problems are reported comparing the efficiency of the algorithm with the results of the studied literature. An analysis of the algorithm behavior for nonconvex test problems is also carried out and finally an analysis of a problem applied to heat exchanger networks is done.