CSSE Seminar Series (CSSESS)
Quick links:
Past seminars,
future seminars,
CSSESS Home
Seminar
Ellipsoid bounds for convex quadratic integer programming
Speaker
Ruth Hübner
Institute
University of Göttingen
Time & Place
3pm, Fri., 8 Feb., in 111, Erskine Building
All are welcome
Abstract
Solving unconstrained convex quadratic integer minimization problems by a branch-and-bound approach requires tight lower bounds on the objective value. We follow the approach by Buchheim, Caprara and Lodi (2011) and underestimate the objective function by a quadratic function that can be easily minimized over the integers. In geometrical terms, we approximate the sublevel set of the objective function by an auxiliary ellipsoid for which we require that the corresponding quadratic integer minimization problem can be solved by rounding the continuous minimizer.
We consider three different classes of auxilliary ellipsoids (characterised by their geometric shape) and show how to efficiently compute an ellipsoid yielding a strong lower bound for each of the classes, respectively, both in the situation where the location of the continuous minimizer is given and in the situation where it varies, as it happens in a branch-and-bound approach. In the latter case, we compute strong bounds both in the worst-case and in the average-case.
Biography
Ruth Hübner is a PhD student supervised by Prof. Anita Schöbel from the University of Göttingen. She also received her Diploma of Mathematics (comparable to MSc) in Göttingen. She works in nonlinear integer optimization and investigates rounding properties for nonlinear integer optimization problems which are based on properties of the level sets of the corresponding objective functions and feasible sets.
Quick links:
Past seminars,
future seminars,
CSSESS Home
