Extensão de limites elipsoidais em programação quadrática inteira

• Ano de defesa: 2017
• Autor(a) principal: Pinillos Nieto, Francisco Ismael
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia de Sistemas e Computação; UFRJ
• Palavras-chave em Português: Engenharia de Sistemas e Computação; Limite elipsoidal; Programação quadrática inteira; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://hdl.handle.net/11422/10165

Ellipsoid bounds for strictly convex quadratic integer programs have been proposed in [1, 2]. The idea is to underestimate the strictly convex quadratic objective function q of the problem by another convex quadratic function with the same continuous minimizer as q and for which an integer minimizer can be easily computed. We propose in this thesis a different way of constructing the quadratic underestimator for the same problem and then extend the idea to other quadratic integer problems, where the objective function is convex (not necessarily strictly convex), and where the objective function is nonconvex and box constraints are introduced. The quality of the proposed bounds is evaluated experimentally and compared to the related existing methodologies.