Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations

• 成果类型: Article
• 署名作者: Qiu, Yuzhou; Yildirim, E. Alper
• 署名单位: University of Edinburgh
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02070-7
• 发表日期: 2025
• 页码: 397-433
• 关键词: branch; bounds

摘要

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.