## Invited Session Wed.3.MA 041

#### Wednesday, 15:15 - 16:45 h, Room: MA 041

**Cluster 14: Mixed-integer nonlinear programming** [...]

### Quadratic integer programming

**Chair: Jeff Linderoth**

**Wednesday, 15:15 - 15:40 h, Room: MA 041, Talk 1**

**Christoph Buchheim**

Nonconvex underestimators for integer quadratic optimization

**Coauthor: Emiliano Traversi**

**Abstract:**

Recently, fast branch-and-bound algorithms for both convex and nonconvex integer quadratic optimization problems have been proposed that use lattice-point free ellipsoids for deriving lower bounds. In the convex case, these bounds improve those obtained from continuous relaxation. The ellipsoids are often chosen as axis-parallel ellipsoids centered in the stationary point of the objective function. In our talk, we show that in this case the resulting lower bound can be interpreted as the integer minimum of a separable quadratic nonconvex global underestimator of the objective function with the same stationary point. The best such underestimator can be computed efficiently by solving an appropriate semidefinite program. This approach can be applied to mixed-integer quadratic programming problems with box constraints, where the separable underestimator can be minimized easily, and to combinatorial optimization problems with quadratic objective functions whenever the underlying linear problem can be solved efficiently.

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

**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.

**Wednesday, 16:15 - 16:40 h, Room: MA 041, Talk 3**

**Hyemin Jeon**

Convex quadratic programming with variable bounds

**Coauthors: Jeffrey T. Linderoth, Andrew J. Miller**

**Abstract:**

The set *X= {(x,z,v) ∈ ***R**_{+}^{n} × **B**^{n} × **R**_{+} | v ≥ x^{T}Qx, x_{j} ≤ z_{j} ∀ j } for some matrix *Q \succeq 0*

appears as substructure in many applications including portfolio management and data mining.

We aim to obtain a good approximation of *\operatorname{conv}(X)*, and our approach starts by reformulating the set using Cholesky factorization *Q = LL*^{T}.

In the reformulated set * S = {(y,t,z,v) ∈ ***R**^{n} × **R**_{+}^{n} × **B**^{n} × **R**_{+} |

v ≥ ∑_{j}t_{j}, t_{j} ≥ y_{j}^{2} ∀ j, 0 ≤ [L^{-T}y]_{j} ≤ z_{j} ∀ j },

the nonlinear constraints are convex and separable but the interaction between continuous and binary variables is more complicated.

Our work thus far has focused on studying the set *S* in the case *n=2* denoted by *S*_{2}.

A number of valid inequalities for *S*_{2} are derived, most of which are represented as second-order cone constraints.

Computational experiments are conducted to empirically compare the obtained relaxation to *\operatorname{conv}(S*_{2}),

and to demonstrate how to utilize our valid inequalities for the case *n>2*.