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


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


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 2k convex quadratic integer programs. Each node of the branch-and-bound algorithm can be processed in O(2kn). 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


The set X= {(x,z,v) ∈ R+n × Bn × R+ | v ≥ xTQx,  xj ≤ zj  ∀ 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 = LLT.
In the reformulated set S = {(y,t,z,v) ∈ Rn × R+n × Bn × R+ |
v ≥ ∑jtj,  tj ≥ yj2  ∀ j,  0 ≤ [L-Ty]j ≤ zj  ∀ 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 S2.
A number of valid inequalities for S2 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}(S2),
and to demonstrate how to utilize our valid inequalities for the case n>2.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.