An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms
An Exact Reformulation Algorithm for Large Nonconvex NLPs Involving Bilinear Terms
复制标题
DOI：
10.1007/s10898-006-9005-4
复制
发表时间：
2006-04
影响因子：
1.8
通讯作者：
Leo Liberti;C. Pantelides
中科院分区：
文献类型：
--
作者：
Leo Liberti;C. Pantelides
许多非凸非线性规划（NLP）问题的实际利益涉及双线性项和线性约束，以及潜在的，其他凸和非凸的条款和约束。在这种情况下，可以用额外的线性约束（Reformulation-Linearization Technique约束的子集）来增加公式，这些约束不影响原始NLP的可行域，但将其凸松弛的可行域收紧到可以从问题公式中删除一些双线性项的程度。我们提出了一个有效的图论算法，实现这种精确的大，稀疏NLP的重新制定。使用空间分支定界算法的重新表达的问题的全局解通常比原始NLP的全局解快得多。我们说明了这一点，我们的算法应用到一组池和混合全局优化问题。
Many nonconvex nonlinear programming (NLP) problems of practical interest involve bilinear terms and linear constraints, as well as, potentially, other convex and nonconvex terms and constraints. In such cases, it may be possible to augment the formulation with additional linear constraints (a subset of Reformulation-Linearization Technique constraints) which do not affect the feasible region of the original NLP but tighten that of its convex relaxation to the extent that some bilinear terms may be dropped from the problem formulation. We present an efficient graph-theoretical algorithm for effecting such exact reformulations of large, sparse NLPs. The global solution of the reformulated problem using spatial Branch-and Bound algorithms is usually significantly faster than that of the original NLP. We illustrate this point by applying our algorithm to a set of pooling and blending global optimization problems.