Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search
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_ | 1866929624647204864 |
|---|---|
| author | Liu, Wenbo Wang, Akang Yang, Wenguo Shi, Qingjiang |
| author_facet | Liu, Wenbo Wang, Akang Yang, Wenguo Shi, Qingjiang |
| contents | Mixed-integer linear programs (MILPs) are extensively used to model practical problems such as planning and scheduling. A prominent method for solving MILPs is large neighborhood search (LNS), which iteratively seeks improved solutions within specific neighborhoods. Recent advancements have integrated machine learning techniques into LNS to guide the construction of these neighborhoods effectively. However, for large-scale MILPs, the search step in LNS becomes a computational bottleneck, relying on off-the-shelf solvers to optimize auxiliary MILPs of substantial size. To address this challenge, we introduce a two-layer LNS (TLNS) approach that employs LNS to solve both the original MILP and its auxiliary MILPs, necessitating the optimization of only small-sized MILPs using off-the-shelf solvers. Additionally, we incorporate a lightweight graph transformer model to inform neighborhood design. We conduct extensive computational experiments using public benchmarks. The results indicate that our learning-based TLNS approach achieves remarkable performance gains--up to 66% and 96% over LNS and state-of-the-art MILP solvers, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08206 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search Liu, Wenbo Wang, Akang Yang, Wenguo Shi, Qingjiang Optimization and Control Mixed-integer linear programs (MILPs) are extensively used to model practical problems such as planning and scheduling. A prominent method for solving MILPs is large neighborhood search (LNS), which iteratively seeks improved solutions within specific neighborhoods. Recent advancements have integrated machine learning techniques into LNS to guide the construction of these neighborhoods effectively. However, for large-scale MILPs, the search step in LNS becomes a computational bottleneck, relying on off-the-shelf solvers to optimize auxiliary MILPs of substantial size. To address this challenge, we introduce a two-layer LNS (TLNS) approach that employs LNS to solve both the original MILP and its auxiliary MILPs, necessitating the optimization of only small-sized MILPs using off-the-shelf solvers. Additionally, we incorporate a lightweight graph transformer model to inform neighborhood design. We conduct extensive computational experiments using public benchmarks. The results indicate that our learning-based TLNS approach achieves remarkable performance gains--up to 66% and 96% over LNS and state-of-the-art MILP solvers, respectively. |
| title | Mixed-Integer Linear Optimization via Learning-Based Two-Layer Large Neighborhood Search |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2412.08206 |