Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2211.08911 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909377243381760 |
|---|---|
| author | Locatelli, Marco Piccialli, Veronica Sudoso, Antonio M. |
| author_facet | Locatelli, Marco Piccialli, Veronica Sudoso, Antonio M. |
| contents | In this paper, we propose a branch-and-bound algorithm for solving nonconvex quadratic programming problems with box constraints (BoxQP). Our approach combines existing tools, such as semidefinite programming (SDP) bounds strengthened through valid inequalities, with a new class of optimality-based linear cuts which leads to variable fixing. The most important effect of fixing the value of some variables is the size reduction along the branch-and-bound tree, allowing to compute bounds by solving SDPs of smaller dimension. Extensive computational experiments over large dimensional (up to $n=200$) test instances show that our method is the state-of-the-art solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class of binary QP problems, where it exhibits competitive performance with state-of-the-art solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_08911 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints Locatelli, Marco Piccialli, Veronica Sudoso, Antonio M. Optimization and Control In this paper, we propose a branch-and-bound algorithm for solving nonconvex quadratic programming problems with box constraints (BoxQP). Our approach combines existing tools, such as semidefinite programming (SDP) bounds strengthened through valid inequalities, with a new class of optimality-based linear cuts which leads to variable fixing. The most important effect of fixing the value of some variables is the size reduction along the branch-and-bound tree, allowing to compute bounds by solving SDPs of smaller dimension. Extensive computational experiments over large dimensional (up to $n=200$) test instances show that our method is the state-of-the-art solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class of binary QP problems, where it exhibits competitive performance with state-of-the-art solvers. |
| title | Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2211.08911 |