Decomposition and relaxation algorithms for nonconvex mixed integer quadratically constrained quadratic programming problems

Activity: Examination typesPre-examination of dissertation or acting as opponent to doctoral students

Fabricio Pinheiro de Oliveira - Examiner

Member of the juri of Phd defense.

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 is 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% in all instances, while Baron achieved relative gaps between 10% and 30% in most of them.
2018
Examination at
  • Pontifical Catholic University of Rio De Janeiro
Examinees
  • Tiago Andrade

ID: 31072234