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" [...]


  Florida Payday Loans can help you in trying times, but be sure to know the laws necessary for your loan application. 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.