  


Quadratic Outer Approximation for Convex Integer Programming
Christoph Buchheim(christoph.buchheimtudortmund.de) Abstract: We present a quadratic outer approximation scheme for solving general convex integer programs, where suitable quadratic approximations are used to underestimate the objective function instead of classical linear approximations. As a resulting surrogate problem 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 integer variables is presented. Our algorithm is based on a fast branchandbound approach for convex quadratic integer programming proposed by Buchheim, Caprara and Lodi [Mathematical Programming 135:369395 (2012)]. The main feature of the latter approach consists in a fast incremental computation of continuous global minima, which are used as lower bounds. We generalize this idea to the case of k convex quadratic functions, implicitly reducing the problem to 2^k1 convex quadratic integer programs. Each node of the branchandbound algorithm can be processed in O(2^kn) time. Experimental results for a class of convex integer problems with exponential objective functions are presented. Compared with Bonmin's outer approximation algorithm BOA and branchandbound algorithm BBB, running times for both ternary and unbounded instances turn out to be very competitive. Keywords: Outer Approximation, Quadratic Programming, Convex Integer Programming Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Nonlinear Optimization (Quadratic Programming ) Category 3: Global Optimization (Other ) Citation: Download: [PDF] Entry Submitted: 02/01/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  