A branch-and-cut algorithm for nonconvex quadratic programs with box constraints (Q1774170)

The aim of this paper is to design an efficient branch-and-cut algorithm for solving linear programs with complementarity constraints of type \[ \begin{align*}{& \! \max {1 \over 2} \sum_{i=1}^n (c_ix_i + y_i) \cr & \text{subject to} \cr & y_i-\sum_{j=1}^n q_{ij}x_j - z_i = c_i, i=\overline{1,n} \cr & y_i(1-x_i)=0, i=\overline{1,n} \cr & z_ix_i=0, i=\overline{1,n} \cr & x_i \leq 1, i=\overline{1,n} \cr & x_i,y_i,z_i \geq 0, i=\overline{1,n}, \cr}\end{align*} \] obtained by reformulating quadratic programs with box constraints of type \[ \begin{align*}{& \! \max {1 \over 2} x^T Q x + c^T x\cr & \text{subject to} \cr & x \in [0,1]^n,\cr}\end{align*} \] where \(Q=[q_{ij}]\) is an \(n \times n\) symmetric matrix. The proposed algorithm uses cutting planes defined by valid inequalities obtained by the authors in their paper [ibid. 102, No. 3 (A), 531--557 (2005; Zbl 1137.90009)]. Considering several branching strategies, the effectiveness of the algorithm is confirmed by computational experiments.