Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914368301563904 |
|---|---|
| author | Kempke, Nils-Christian Koch, Thorsten |
| author_facet | Kempke, Nils-Christian Koch, Thorsten |
| contents | We investigate the use of low-precision first-order methods (FOMs) within a fix-and-propagate (FP) framework for solving mixed-integer programming problems (MIPs). We employ GPU-accelerated PDLP, a variant of the Primal-Dual Hybrid Gradient (PDHG) method specialized to LP problems, to solve the \LP-relaxation of our MIPs to low accuracy. This solution is used to motivate fixings within our FP framework. We evaluate the performance of our heuristic on MIPLIB 2017, demonstrating that low-accuracy LP solutions do not lead to a loss in the quality of the FP heuristic solutions. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million nonzeros and 8 million decision variables) unit commitment-based dispatch and expansion planning problems created with the modeling framework REMix. For the largest problems, we can generate solutions with a primal-dual gap of under 2% in less than 4 hours, whereas state-of-the-art commercial solvers cannot produce feasible solutions within 2 days of runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_10344 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization Kempke, Nils-Christian Koch, Thorsten Optimization and Control 90-08 (Primary), 90C06, 90C11, 90C59, 90C90 (Secondary) We investigate the use of low-precision first-order methods (FOMs) within a fix-and-propagate (FP) framework for solving mixed-integer programming problems (MIPs). We employ GPU-accelerated PDLP, a variant of the Primal-Dual Hybrid Gradient (PDHG) method specialized to LP problems, to solve the \LP-relaxation of our MIPs to low accuracy. This solution is used to motivate fixings within our FP framework. We evaluate the performance of our heuristic on MIPLIB 2017, demonstrating that low-accuracy LP solutions do not lead to a loss in the quality of the FP heuristic solutions. Further, we use our FP framework to produce high-accuracy solutions for large-scale (up to 243 million nonzeros and 8 million decision variables) unit commitment-based dispatch and expansion planning problems created with the modeling framework REMix. For the largest problems, we can generate solutions with a primal-dual gap of under 2% in less than 4 hours, whereas state-of-the-art commercial solvers cannot produce feasible solutions within 2 days of runtime. |
| title | Fix-and-Propagate Heuristics Using Low-Precision First-Order LP Solutions for Large-Scale Mixed-Integer Linear Optimization |
| topic | Optimization and Control 90-08 (Primary), 90C06, 90C11, 90C59, 90C90 (Secondary) |
| url | https://arxiv.org/abs/2503.10344 |