
The authors present a branch and cut algorithm that yields in finite time, a globally \(\varepsilon\)-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 linearization within a branching tree using reformulation-linearization techniques. To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, the authors 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 computation speed, the structure created at any node of the three 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.
outer-approximation, branch and cut algorithm, RTL-linearization, global optimization, Polyhedral combinatorics, branch-and-bound, branch-and-cut, quadratic programming, Quadratic programming, Nonconvex programming, global optimization, nonconvex programming
outer-approximation, branch and cut algorithm, RTL-linearization, global optimization, Polyhedral combinatorics, branch-and-bound, branch-and-cut, quadratic programming, Quadratic programming, Nonconvex programming, global optimization, nonconvex programming
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 140 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
