[pt] ALGORITMOS BASEADOS EM DECOMPOSIÇÃO E RELAXAÇÃO PARA PROBLEMAS DE PROGRAMAÇÃO INTEIRA MISTA QUADRÁTICA COM RESTRIÇÕES QUADRÁTICAS NÃO CONVEXA

[en] DECOMPOSITION AND RELAXATION ALGORITHMS FOR NONCONVEX MIXED INTEGER QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING PROBLEMS

[pt] TIAGO COUTINHO CARNEIRO DE ANDRADE

[pt] DECOMPOSICAO

[pt] TECNICA DE DESAGREGACAO MULTIPARAMETRICA NORMALIZADA

[pt] RELAXACAO CONVEXA

[pt] PROGRAMACAO QUADRATICA COM RESTRICOES QUADRATICAS

[pt] PROGRAMACAO INTEIRA MISTA

[pt] RELAXACAO LAGRANGEANA

[en] DECOMPOSITION

[en] NORMALIZED MULTIPARAMETRIC DISAGGREGATION TECHNIQUE

[en] CONVEX RELAXATION

[en] QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING

[en] MIXED INTEGER PROGRAMMING

[en] LAGRANGEAN RELAXATION

[pt] 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.

[en] 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.

SILVIO HAMACHER

FABRICIO CARLOS PINHEIRO OLIVEIRA

SILVIO HAMACHER

SERGIO GRANVILLE

BRUNO FANZERES DOS SANTOS

FABRICIO CARLOS PINHEIRO OLIVEIRA

RAFAEL MARTINELLI PINTO

FERNANDA MARIA PEREIRA RAUPP

2019-04-29

2018-12-13

[pt] TEXTO

application/pdf

INGLÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=37845@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=37845@2

https://doi.org/10.17771/PUCRio.acad.37845