**Friday, 15:45 - 16:10 h, Room: H 3005**

**Ruth Hübner**

Ellipsoid bounds for convex quadratic integer programming

**Coauthors: Christoph Buchheim, Anita Schöbel**

**Abstract:**

Solving unrestricted convex quadratic integer programs by a branch&bound approach requires lower bounds on the objective value. We are going to follow the approach by Buchheim, Caprara and Lodi (2011) and approximate the quadratic function by an "easier'' quadratic function which underestimates the original one. Geometrically, we approximate the level set of the objective by an auxiliary ellipsoid for which we require that the corresponding quadratic integer problem can be solved by rounding its continuous optimal solution. In a first approach we are going to restrict the choice of the auxiliary ellipsoid to axis-parallel ellipsoids (corresponding to the level sets of separable convex quadratic functions). Which one is the "best'' auxiliary axis-parallel ellipsoid depends not only on the given objective function but also on the respective continuous optimal solution which changes in every node of the branching tree. As it is expensive to find a good auxiliary ellipsoid we want to decide on a single ellipsoid and use it for the whole algorithm. This raises the question on how to compare different ellipsoids. To this end, worst-case and average-case arguments are discussed.

Talk 2 of the invited session Fri.3.H 3005

**"Nonlinear combinatorial optimization problems II"** [...]

Cluster 2

**"Combinatorial optimization"** [...]