Optimization Online


Active Set Methods with Reoptimization for Convex Quadratic Integer Programming

Christoph Buchheim (christoph.buchheim***at***tu-dortmund.de)
Long Trieu (long.trieu***at***tu-dortmund.de)

Abstract: We present a fast branch-and-bound algorithm for solving convex quadratic integer programs with few linear constraints. In each node, we solve the dual problem of the continuous relaxation using an infeasible active set method proposed by Kunisch and Rendl to get a lower bound; this active set algorithm is well suited for reoptimization. Our algorithm generalizes a branch-and-bound approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara and Lodi to the presence of linear constraints. The main feature of the latter approach consists in a sophisticated preprocessing phase, leading to a fast enumeration of the branch-and-bound nodes. Experimental results for randomly generated instances are presented. The new approach significantly outperforms the MIQP solver of CPLEX 12.4 for instances with a small number of constraints.

Keywords: Branch-and-Bound, Active Set Method, Convex Quadratic Integer Programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: The article was published in the conference proceedings of ISCO 2014: http://dx.doi.org/10.1007/978-3-319-09174-7_11


Entry Submitted: 12/11/2013
Entry Accepted: 12/11/2013
Entry Last Modified: 12/02/2014

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