**Wednesday, 15:45 - 16:10 h, Room: MA 041**

**Long Trieu**

Convex piecewise quadratic integer programming

**Coauthor: Christoph Buchheim**

**Abstract:**

We consider the problem of minimizing a function given as the maximum of finitely many convex quadratic functions having the same Hessian matrix. A fast algorithm for minimizing such functions over all integer vectors is presented. This algorithm can be embedded in an extended outer approximation scheme for solving general convex integer programs, where suitable quadratic approximations are used to underestimate the original objective function instead of classical linear approximations. Our algorithm is based on a fast branch-and-bound approach for convex quadratic integer programming proposed by Buchheim, Caprara and Lodi (2011). The main feature of the latter approach consists in a fast incremental computation of continuous global minima, which are used as lower bounds. We explain the generalization of this idea to the case of *k* convex quadratic functions. The idea is to implicitly reduce the problem to at most *2*^{k} convex quadratic integer programs. Each node of the branch-and-bound algorithm can be processed in *O(2*^{k}n). Experimental results for increasing sizes of *k* are shown. Compared to the standard MIQCP solver of CPLEX, running times can be improved considerably.

Talk 2 of the invited session Wed.3.MA 041

**"Quadratic integer programming"** [...]

Cluster 14

**"Mixed-integer nonlinear programming"** [...]