A Massively Parallel Interior-Point Method for Arrowhead Linear Programs with Local Linking Structure
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917392935813120 |
|---|---|
| author | Kempke, Nils-Christian Rehfeldt, Daniel Koch, Thorsten |
| author_facet | Kempke, Nils-Christian Rehfeldt, Daniel Koch, Thorsten |
| contents | In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints' locality to decouple the factorization process. Our approach is motivated by large-scale unit commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_07731 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Massively Parallel Interior-Point Method for Arrowhead Linear Programs with Local Linking Structure Kempke, Nils-Christian Rehfeldt, Daniel Koch, Thorsten Optimization and Control 90C05, 90C51 (Primary), 65F05, 65K05, 65Y05, 90C06, 90-08 (Secondary) In practice, non-specialized interior point algorithms often cannot utilize the massively parallel compute resources offered by modern many- and multi-core compute platforms. However, efficient distributed solution techniques are required, especially for large-scale linear programs. This article describes a new decomposition technique for systems of linear equations implemented in the parallel interior-point solver PIPS-IPM++. The algorithm exploits a matrix structure commonly found in optimization problems: a doubly-bordered block-diagonal or arrowhead structure. This structure is preserved in the linear KKT systems solved during each iteration of the interior-point method. We present a hierarchical Schur complement decomposition that distributes and solves the linear optimization problem; it is designed for high-performance architectures and scales well with the availability of additional computing resources. The decomposition approach uses the border constraints' locality to decouple the factorization process. Our approach is motivated by large-scale unit commitment problems. We demonstrate the performance of our method on a set of mid-to large-scale instances, some of which have more than 10^9 nonzeros in their constraint matrix. |
| title | A Massively Parallel Interior-Point Method for Arrowhead Linear Programs with Local Linking Structure |
| topic | Optimization and Control 90C05, 90C51 (Primary), 65F05, 65K05, 65Y05, 90C06, 90-08 (Secondary) |
| url | https://arxiv.org/abs/2412.07731 |