-

 

 

 




Optimization Online





 

Global Optimization of Mixed-Integer Quadratically-Constrained Quadratic Programs (MIQCQP) through Piecewise-Linear and Edge-Concave Relaxations

R. Misener (r.misener***at***imperial.ac.uk)
C. A. Floudas (floudas***at***titan.princeton.edu)

Abstract: We propose a deterministic global optimization approach, whose novel contributions are rooted in the edge-concave and piecewise-linear underestimators, to address nonconvex mixed-integer quadratically-constrained quadratic programs (MIQCQP) to epsilon-global optimality. The facets of low-dimensional (n < 4) edge-concave aggregations dominating the termwise relaxation of MIQCQP are introduced at every node of a branch-and-bound tree. Concave multivariable terms and sparsely distributed bilinear terms that do not participate in connected edge-concave aggregations are addressed through piecewise-linear relaxations. Extensive computational studies are presented for point packing problems, standard and generalized pooling problems, and examples from GLOBALLib [55].

Keywords:

Category 1: Global Optimization

Citation: Mathematical Programming; 136 (1) pp. 155-182; 2012 (DOI 10.1007/s10107-012-0555-6)

Download: [PDF]

Entry Submitted: 11/14/2011
Entry Accepted: 11/14/2011
Entry Last Modified: 04/28/2013

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society