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


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.


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


  To apply for USA Payday Loans you don't have to seek the help of relatives or go to a bank. This is a permit to the world of pleasure and the lasting sex. Cialis Super Active online is a drug, the quality level of which is determined by its action speed.