Optimization Online


Quadratic Outer Approximation for Convex Integer Programming

Christoph Buchheim(christoph.buchheim***at***tu-dortmund.de)
Long Trieu(long.trieu***at***tu-dortmund.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 branch-and-bound approach for convex quadratic integer programming proposed by Buchheim, Caprara and Lodi [Mathematical Programming 135:369-395 (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^k-1 convex quadratic integer programs. Each node of the branch-and-bound 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 B-OA and branch-and-bound algorithm B-BB, 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 )


Download: [PDF]

Entry Submitted: 02/01/2013
Entry Accepted: 02/01/2013
Entry Last Modified: 02/01/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society