A branch and cut algorithm for nonconvex quadratically constrained quadratic programming

摘要: We present a branch and cut algorithm that yields in finite time, globally e-optimal solution (with respect to feasibility optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is estimate all terms by successive linearizations within branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes (cuts), depending on one three parameters, are detailed. For each class, we show how select best member with precise criterion. cuts introduced at any node valid whole tree, not only subtree rooted node. In order enhance computational speed, structure created flexible enough be used other nodes. Computational results reported include standard test problems taken from literature. Some these solved for first time proof global optimality.