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

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.