Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |