A Binarisation Approach to Non-Convex Quadratically Constrained Quadratic Programs
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.
Entry Submitted: 05/20/2015
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|