DECOMPOSITION AND RELAXATION ALGORITHMS FOR NONCONVEX MIXED INTEGER QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING PROBLEMS
| Autor: | TIAGO COUTINHO CARNEIRO DE ANDRADE |
|---|---|
| Přispěvatelé: | SILVIO HAMACHER, FABRICIO CARLOS PINHEIRO OLIVEIRA, FERNANDA MARIA PEREIRA RAUPP, RAFAEL MARTINELLI PINTO |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Zdroj: | Repositório Institucional da PUC-RIO (Projeto Maxwell) Pontifícia Universidade Católica do Rio de Janeiro (PUC-RIO) instacron:PUC_RIO |
| Popis: | PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO FUNDAÇÃO DE APOIO À PESQUISA DO ESTADO DO RIO DE JANEIRO BOLSA NOTA 10 PROGRAMA DE DOUTORADO SANDUÍCHE NO EXTERIOR PROGRAMA DE SUPORTE À PÓS-GRADUAÇÃO DE INSTITUIÇÕES COMUNITÁRIAS DE ENSINO PARTICULARES Esta tese investiga e desenvolve algoritmos baseados em relaxação Lagrangiana e técnica de desagregação multiparamétrica normalizada para resolver problemas não convexos de programação inteira-mista quadrática com restrições quadráticas. Primeiro, é realizada uma revisão de técnias de relaxação para este tipo de problema e subclasses do mesmo. Num segundo momento, a técnica de desagregação multiparamétrica normalizada é aprimorada para sua versão reformulada onde o tamanho dos subproblemas a serem resolvidos tem seu tamanho reduzido, em particular no número de variáveis binárias geradas. Ademais, dificuldas em aplicar a relaxação Lagrangiana a problemas não convexos são discutidos e como podem ser solucionados caso o subproblema dual seja substituído por uma relaxação não convexa do mesmo. Este método Lagrangiano modificado é comparado com resolvedores globais comerciais e resolvedores de código livre. O método proposto convergiu em 35 das 36 instâncias testadas, enquanto o Baron, um dos resolvedores que obteve os melhores resultados, conseguiu convergir apenas para 4 das 36 instâncias. Adicionalmente, mesmo para a única instância que nosso método não conseguiu resolver, ele obteve um gap relativo de menos de 1 por cento, enquanto o Baron atingiu um gap entre 10 por cento e 30 por cento para a maioria das instâncias que o mesmo não convergiu. This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming. First, relaxations for quadratic programming and related problem classes are reviewed. Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables. Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations. This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances. The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36. Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1 percent in all instances, while Baron achieved relative gaps between 10 percent and 30 percent in most of them. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|