The convex hull relaxation (CHR) method (Albornoz 1998, Ahlatçıoğlu 2007, Ahlatçıoğlu and Guignard 2010) provides lower bounds and feasible solutions (thus upper bounds) on convex 0-1 nonlinear programming problems with linear constraints. In the quadratic case, these bounds may often be improved by a preprocessing step that adds to the quadratic objective function terms which are equal to 0 for all 0-1 feasible solutions yet increase its continuous minimum. Prior to (or in addition to) computing CHR bounds, one may use Plateau’s quadratic convex reformulation (QCR) method (2006), or one of its weaker predecessors designed for unconstrained problems, the eigenvalue method of Hammer and Rubin (1970) or the method of Billionnet and Elloumi (2007). In this paper, we first describe the CHR method, and then present the essentials of the QCR reformulation methods. We present computational results for convex GQAP problems using CHR, preceded or not by Plateau’s QCR.
Citation
Department of OPIM Research Report, Oct. 2010, the Wharton School, University of Pennsylvania
Article
View Combining QCR and CHR for Convex Quadratic MINLP Problems with Linear Constraints