Novas Abordagens de Solução para Programação Não Linear Inteira Mista Binária e Programção Quadrática Não Convexa
Autores
|
5949 |
2337,603,721,2740
|
|
|
5950 |
2337,603,721,2740
|
|
|
5951 |
2337,603,721,2740
|
|
|
5952 |
Jon Lee
(Co-orientador) |
2337,603,721,2740
|
Informações:
Publicações do PESC
Título
Novas Abordagens de Solução para Programação Não Linear Inteira Mista Binária e Programção Quadrática Não Convexa
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
3/3/2016
Resumo
Este trabalho é fundamentalmente dividido em duas partes. Na primeira parte, elaboramos uma nova metodologia para a abordagem do problema convexo de Programação Não Linear Inteira Mista (PNLIM) binária. Apresentamos aqui duas versões de um algoritmo exato para solucionar o problema mencionado baseadas na ideia de minimização do gap de integralidade. Demonstramos aqui a convergência dos algoritmos em número finito de iterações. As abordagens propostas podem localizar soluções viáveis rapidamente, habilitando assim seu uso na qualidade de heurística de viabilidade. Na segunda parte, tratamos do problema de otimização global onde os termos não convexos se remetem a expressões quadráticas na função objetivo e/ou restrições. Desenvolvemos uma abordagem baseada em decomposição por Diferença de duas funções Convexas (DC) para a construção de relaxações convexas adotadas em um procedimento de Branch-and-Bound Espacial (BBE). Apresentamos diferentes estratégias de decomposição e demonstramos a equivalência de algumas das mesmas. Em ambas as partes, fornecemos resultados computacionais promissores. Complementarmente às contribuições teóricas, desenvolvemos contribuições práticas por meio de pacotes computacionais que implementam as abordagens aqui descritas. Estes pacotes computacionais serão disponibilizados à comunidade técnica e científica para uso livre.
Abstract
This thesis is divided into two parts. In the first one, we develop a new methodology to treat binary Mixed Integer NonLinear Programming (MINLP) problems. We present two versions of an exact algorithm to solve the addressed problem based on integrality gap minimization. We demonstrate the convergence of the algorithms in a finite number of iterations. The proposed approaches can find feasible solutions quickly, enabling its usage as a feasibility heuristic. In the second part, we deal with the global optimization problem where noncmonvex terms only appear in quadratic expressions in the objective function and/or constraints. We develop an approach based on the Difference of two Convex functions (DC) in order to build a convex relaxation to be used in a Spatial Branch-And-Bound procedure. We present different decomposition strategies and we prove the equivalence of some of the. In both parts, we provide promising computational results. We also develop practical contributions by means of computational packages that implement the approaches described here. Those packages will be available to technicians and researchers for free usage.
Arquivo