Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations

• 成果类型: Article
• 署名作者: Misener, Ruth; Floudas, Christodoulos A.
• 署名单位: Princeton University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0555-6
• 发表日期: 2012
• 页码: 155-182
• 关键词: bilinear programs; nonconvex nlps; alpha-bb; distillation sequences; pooling problems; bound algorithm; cut algorithm; convex; networks; branch

摘要

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 <= 3) 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 (Meeraus, Globallib. http://www.gamsworld.org/global/globallib.htm).