Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/10165
Type: Tese
Title: Extensão de limites elipsoidais em programação quadrática inteira
Author(s)/Inventor(s): Pinillos Nieto, Francisco Ismael
Advisor: Fampa, Marcia Helena Costa
Abstract: Limites elipsoidais para problemas de programação inteira estritamente convexa foram propostos em [1, 2]. A ideia é subestimar a função objetivo quadrática q do problema por outra função quadrática convexa com o mesmo minimizador contínuo da função q e para a qual um minimizador inteiro pode ser facilmente calculado. Propomos nesta tese uma maneira diferente de construir o subestimador quadrático para o mesmo problema e então estender a ideia a outros problemas inteiros quadráticos, onde a função objetivo é convexa (não necessariamente estritamente convexa), e onde a função objetivo é não convexa com a introdução de restrições de caixa. A qualidade dos limites propostos é avaliada experimentalmente e comparada com as metodologias relacionadas.
Abstract: 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.
Keywords: Engenharia de Sistemas e Computação
Limite elipsoidal
Programação quadrática inteira
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Department : Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Mar-2017
Publisher country: Brasil
Language: por
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
878074.pdf2,2 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.