Programação não linear inteira mista e não convexa sem derivadas

Abstract

Vários problemas da área do planeamento de processos de engenharia são modelados como problemas de programação não linear inteira mista (PNLIM), em que as variáveis de decisão são contínuas e inteiras. Nos processos mais complexos, as funções envolvidas no problema, nomeadamente a função objetivo e as funções de restrição, são não convexas e eventualmente não suaves. Este tipo de problemas de otimização são difíceis de resolver e são o foco principal desta tese. Assim, o objetivo principal deste estudo é desenvolver algoritmos eficazes que não exijam o cálculo de derivadas e sejam capazes de convergir para as soluções de problemas de PNLIM não convexos. Duas abordagens diferentes são propostas para a resolução de problemas de PNLIM. Uma, é uma técnica híbrida de partição e avaliação (BB) uma vez que combina o paradigma BB com uma estratégia estocástica de otimização do tipo de iniciação múltipla, de tal forma que seja garantida com probabilidade um a convergência para uma solução global de um problema de relaxação contínua de programação não linear (PNL). O método, conotado BBMCSFilter, conta com um algoritmo de procura sobre as coordenadas baseado no método dos filtros para convergir para minimizantes, a partir de um qualquer ponto retirado do espaço de procura. A segunda abordagem, designada por MS+m-HJ-f, faz uma extensão da estratégia de iniciação múltipla para poder tratar simultaneamente as variáveis contínuas e inteiras. O método de procura direta Hooke-and-Jeeves é modificado por forma a manusear variáveis inteiras mistas e tratar restrições de desigualdade e igualdade pelo método dos filtros. Este método também foi desenvolvido com o objetivo de calcular múltiplas soluções de problemas de PNLIM. As experiências numéricas realizadas com as novas abordagens mostram que os algoritmos propostos são eficazes. Foram obtidas soluções de qualidade mais elevada com velocidades de convergência, em termos de avaliações das funções e do tempo de computação, ligeiramente superiores quando comparadas com outras técnicas disponíveis na literatura.

Several problems in engineering process design are modeled as mixed-integer nonlinear programming (MINLP) problems, where the decision variables are continuous and integer. In the most complex processes, the involved functions, namely the objective and the constraint functions, are non-convex and eventually non-smooth. This type of optimization problems are difficult to solve and are the main focus of this thesis. Thus, the main goal of this study is to develop effective algorithms that do not require derivative information and are capable of converging to the solutions of non-convex MINLP problems. Two different approaches are proposed for MINLP. One is a hybrid branch and bound (BB) technique in the sense that combines the BB paradigm with a stochastic optimization multistart strategy, so that convergence to a global solution of a nonlinear programming (NLP) continuous relaxation problem is guaranteed with probability one. The method, coined BBMCSFilter, relies on a coordinate search filter-based algorithm to converge to minimizers, from any sampled point in the search space. The second approach, denoted by MS+m-HJ-f, extends the multistart strategy to be able to handle continuous and integer variables simultaneously. The direct search Hooke-and-Jeeves method is modified in order to address mixed integer variables and to handle inequality and equality constraints by the filter method. This method has also been designed to determine multiple solutions to MINLP problems. Numerical experiments carried out with these new approaches show that the proposed algorithms are effective. Higher quality solutions with convergence speed, in terms of function evaluations and computation time, slightly superior are obtained when compared with other techniques available in the literature.