Wednesday, 15:15 - 15:40 h, Room: MA 041


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.


Talk 1 of the invited session Wed.3.MA 041
"Quadratic integer programming" [...]
Cluster 14
"Mixed-integer nonlinear programming" [...]


  signature loans . Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.