Optimization Online


A Fast Branch-and-Bound Algorithm for Non-convex Quadratic Integer Optimization Subject To Linear Constraints Using Ellipsoidal Relaxations

Christoph Buchheim (christoph.buchheim***at***math.tu-dortmund.de)
Marianna De Santis (marianna.de.santis***at***math.tu-dortmund.de)
Laura Palagi (laura.palagi***at***uniroma1.it)

Abstract: We propose two exact approaches for non-convex quadratic integer minimization subject to linear constraints where lower bounds are computed by considering ellipsoidal relaxations of the feasible set. In the first approach, we intersect the ellipsoids with the feasible linear subspace. In the second approach we penalize exactly the linear constraints. We investigate the connection between both approaches theoretically. Experimental results show that the penalty approach significantly outperforms CPLEX on problems with small or medium size variable domains.

Keywords: integer programming; quadratic programming; global optimization

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

Category 2: Global Optimization

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Operations Research Letters, 43(4), pp.384-388, (2015)

Download: [PDF]

Entry Submitted: 02/06/2015
Entry Accepted: 02/06/2015
Entry Last Modified: 07/28/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