Academic Journal
Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations
| العنوان: | Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations |
|---|---|
| المؤلفون: | Qiu, Yuzhou, Yıldırım, E. Alper |
| المصدر: | Mathematical Programming ; volume 209, issue 1-2, page 397-433 ; ISSN 0025-5610 1436-4646 |
| بيانات النشر: | Springer Science and Business Media LLC |
| سنة النشر: | 2024 |
| الوصف: | 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. |
| نوع الوثيقة: | article in journal/newspaper |
| اللغة: | English |
| DOI: | 10.1007/s10107-024-02070-7 |
| DOI: | 10.1007/s10107-024-02070-7.pdf |
| DOI: | 10.1007/s10107-024-02070-7/fulltext.html |
| الاتاحة: | https://doi.org/10.1007/s10107-024-02070-7 https://link.springer.com/content/pdf/10.1007/s10107-024-02070-7.pdf https://link.springer.com/article/10.1007/s10107-024-02070-7/fulltext.html |
| Rights: | https://creativecommons.org/licenses/by/4.0 ; https://creativecommons.org/licenses/by/4.0 |
| رقم الانضمام: | edsbas.329479EB |
| قاعدة البيانات: | BASE |
| DOI: | 10.1007/s10107-024-02070-7 |
|---|