Progressively Strengthening and Tuning MIP Solvers for Reoptimization
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929222937739264 |
|---|---|
| author | Patel, Krunal Kishor |
| author_facet | Patel, Krunal Kishor |
| contents | This paper explores reoptimization techniques for solving sequences of similar mixed integer programs (MIPs) more effectively. Traditionally, these MIPs are solved independently, without capitalizing on information from previously solved instances. Our approach focuses on primal bound improvements by reusing the solutions of the previously solved instances, as well as dual bound improvements by reusing the branching history and automating parameter tuning. We also describe ways to improve the solver performance by extending ideas from reliability branching to generate better pseudocosts. Our reoptimization approach, crafted for the MIP 2023 workshop computational competition, was honored with the first prize. In this paper, we thoroughly analyze the performance of each technique and their combined impact on the solver's performance. Finally, we present ways to extend our techniques in practice for further improvements. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_08986 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Progressively Strengthening and Tuning MIP Solvers for Reoptimization Patel, Krunal Kishor Optimization and Control 90C11 (Primary), 90C10, 90-08 (Secondary) This paper explores reoptimization techniques for solving sequences of similar mixed integer programs (MIPs) more effectively. Traditionally, these MIPs are solved independently, without capitalizing on information from previously solved instances. Our approach focuses on primal bound improvements by reusing the solutions of the previously solved instances, as well as dual bound improvements by reusing the branching history and automating parameter tuning. We also describe ways to improve the solver performance by extending ideas from reliability branching to generate better pseudocosts. Our reoptimization approach, crafted for the MIP 2023 workshop computational competition, was honored with the first prize. In this paper, we thoroughly analyze the performance of each technique and their combined impact on the solver's performance. Finally, we present ways to extend our techniques in practice for further improvements. |
| title | Progressively Strengthening and Tuning MIP Solvers for Reoptimization |
| topic | Optimization and Control 90C11 (Primary), 90C10, 90-08 (Secondary) |
| url | https://arxiv.org/abs/2308.08986 |