Optimization Online


A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming

Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de)
Stefano Lucidi (lucidi***at***dis.uniroma1.it)
Marianna De Santis (msantis***at***math.tu-dortmund.de)
Francesco Rinaldi (rinaldi***at***math.unipd.it)
Long Trieu (long.trieu***at***math.tu-dortmund.de)

Abstract: We propose a feasible active set method for convex quadratic programming problems with non-negativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed integer programming problems. The branch-and-bound algorithm generalizes the 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. Moreover, the feasible active set method takes advantage of this preprocessing phase and is well suited for reoptimization. Experimental results for randomly generated instances show that the new approach significantly outperforms the MIQP solver of CPLEX 12.6 for instances with a small number of constraints.

Keywords: integer programming, quadratic programming, global optimization

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

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: SIAM Journal on Optimization, 26(3), pp. 1695-1714, (2016).

Download: [PDF]

Entry Submitted: 07/23/2014
Entry Accepted: 07/23/2014
Entry Last Modified: 12/20/2016

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