caa a22 4500 475769198 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000101xx s 000 0 eng 10.1007/s101079900106 doi (NATIONALLICENCE)springer-10.1007/s101079900106 A branch and cut algorithm for nonconvex quadratically constrained quadratic programming [Elektronische Daten] [Charles Audet, Pierre Hansen, Brigitte Jaumard, Gilles Savard] Abstract. : We present a branch and cut algorithm that yields in finite time, a globally ε-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 of 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. Springer-Verlag Berlin Heidelberg, 2000 Key words: nonconvex programming - quadratic programming - RLT - linearization - outer-approximation - branch and cut - global optimization nationallicence Audet Charles Rice University, CAAM - MS134, 6100 Main Street, Houston, Texas, 77005-1892, USA, e-mail: charlesa@caam.rice.edu, US aut Hansen Pierre GERAD and École des Hautes Études Commerciales, Département MQ, 5255 avenue Decelles, Montréal (Québec), H3T 1V6, Canada, e-mail: pierreh@crt.umontreal.ca, CA aut Jaumard Brigitte GERAD and École Polytechnique de Montréal, Département de Mathématiques et de Génie Industriel, C.P. 6079, Succursale "Centre-Ville”, Montréal (Québec), H3C 3A7, Canada, e-mail: {brigitt, gilles}@crt.umontreal.ca, CA aut Savard Gilles GERAD and École Polytechnique de Montréal, Département de Mathématiques et de Génie Industriel, C.P. 6079, Succursale "Centre-Ville”, Montréal (Québec), H3C 3A7, Canada, e-mail: {brigitt, gilles}@crt.umontreal.ca, CA aut https://doi.org/10.1007/s101079900106 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s101079900106 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Audet Charles Rice University, CAAM - MS134, 6100 Main Street, Houston, Texas, 77005-1892, USA, e-mail: charlesa@caam.rice.edu, US aut NATIONALLICENCE 700 1- Hansen Pierre GERAD and École des Hautes Études Commerciales, Département MQ, 5255 avenue Decelles, Montréal (Québec), H3T 1V6, Canada, e-mail: pierreh@crt.umontreal.ca, CA aut NATIONALLICENCE 700 1- Jaumard Brigitte GERAD and École Polytechnique de Montréal, Département de Mathématiques et de Génie Industriel, C.P. 6079, Succursale "Centre-Ville”, Montréal (Québec), H3C 3A7, Canada, e-mail: {brigitt, gilles}@crt.umontreal.ca, CA aut NATIONALLICENCE 700 1- Savard Gilles GERAD and École Polytechnique de Montréal, Département de Mathématiques et de Génie Industriel, C.P. 6079, Succursale "Centre-Ville”, Montréal (Québec), H3C 3A7, Canada, e-mail: {brigitt, gilles}@crt.umontreal.ca, CA aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer