Extensão de Limites Elipsoidais em Programação Quadrática Inteira
Autores
|
6399 |
2831,603
|
|
|
6400 |
2831,603
|
Informações:
Publicações do PESC
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.
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.