Optimization Online


A Binarisation Approach to Non-Convex Quadratically Constrained Quadratic Programs

Laura Galli(laura.galli***at***unipi.it)
Adam N Letchford(A.N.Letchford***at***lancaster.ac.uk)

Abstract: Global optimisation of non-convex quadratically constrained quadratic programs is a notoriously difficult problem, being not only NP-hard in the strong sense, but also very difficult in practice. We present a new heuristic approach to this problem, which enables one to obtain solutions of good quality in reasonable computing times. The heuristic consists of four phases: binarisation, convexification, branch-and-bound and local optimisation. Computational results, on box-constrained and point packing instances, are encouraging.

Keywords: quadratically constrained quadratic programming; mixed-integer nonlinear programming; heuristics

Category 1: Global Optimization

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

Category 3: Nonlinear Optimization (Quadratic Programming )

Citation: Working paper, Department of Management Science, Lancaster University, February 2015.

Download: [PDF]

Entry Submitted: 05/20/2015
Entry Accepted: 05/20/2015
Entry Last Modified: 05/20/2015

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