期刊
MATHEMATICAL PROGRAMMING
卷 87, 期 1, 页码 131-152出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s101079900106
关键词
nonconvex programming; quadratic programming; RLT; linearization; outer-approximation; branch and cut; global optimization
We present a branch and cut algorithm that yields in finite time, a globally epsilon-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node df the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据