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].


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


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