Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations
研究了非凸二次规划的RLT松弛的多面体性质，建立了可行域与松弛之间的退缩方向、有界性和顶点关系，给出了精确RLT松弛的实例完整描述，并讨论了如何构造精确、非精确或无界松弛的实例。
Abstract We study linear programming relaxations of nonconvex quadratic programs given by the reformulation–linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. Using these properties, we present a complete description of the set of instances that admit an exact RLT relaxation. We then give a thorough discussion of how our results can be converted into simple algorithmic procedures to construct instances of quadratic programs with exact, inexact, or unbounded RLT relaxations.