Logo PUC-Rio Logo Maxwell
ETDs @PUC-Rio
Estatística
Título: DECOMPOSITION AND RELAXATION ALGORITHMS FOR NONCONVEX MIXED INTEGER QUADRATICALLY CONSTRAINED QUADRATIC PROGRAMMING PROBLEMS
Autor: TIAGO COUTINHO CARNEIRO DE ANDRADE
Colaborador(es): SILVIO HAMACHER - Orientador
FABRICIO CARLOS PINHEIRO OLIVEIRA - Coorientador
Catalogação: 29/ABR/2019 Língua(s): ENGLISH - UNITED STATES
Tipo: TEXT Subtipo: THESIS
Notas: [pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
[en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio.
Referência(s): [pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=37845&idi=1
[en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=37845&idi=2
DOI: https://doi.org/10.17771/PUCRio.acad.37845
Resumo:
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.
Descrição: Arquivo:   
COMPLETE PDF