A factorisation-based regularised interior point method using the augmented system
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915431878492160 |
|---|---|
| author | Zanetti, Filippo Gondzio, Jacek |
| author_facet | Zanetti, Filippo Gondzio, Jacek |
| contents | This paper describes the implementation of a new interior point solver for linear programming for the open-source optimization library HiGHS. The solver uses a direct factorisation to solve the Newton systems, choosing the best approach between the normal equations and augmented system. Details of the multifrontal factorisation routine are given, with attention to the features that allow to achieve high performance, like storage formats, use of efficient dense linear algebra subroutines and parallelism. The paper also describes the use of pivoting and regularisation strategies to ensure that a stable factorisation is obtained, despite the ill-conditioning of the matrices. Results on three different collections of problems are presented which highlight the improved performance of the solver compared to the existing HiGHS interior point method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04370 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A factorisation-based regularised interior point method using the augmented system Zanetti, Filippo Gondzio, Jacek Optimization and Control This paper describes the implementation of a new interior point solver for linear programming for the open-source optimization library HiGHS. The solver uses a direct factorisation to solve the Newton systems, choosing the best approach between the normal equations and augmented system. Details of the multifrontal factorisation routine are given, with attention to the features that allow to achieve high performance, like storage formats, use of efficient dense linear algebra subroutines and parallelism. The paper also describes the use of pivoting and regularisation strategies to ensure that a stable factorisation is obtained, despite the ill-conditioning of the matrices. Results on three different collections of problems are presented which highlight the improved performance of the solver compared to the existing HiGHS interior point method. |
| title | A factorisation-based regularised interior point method using the augmented system |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2508.04370 |