Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910296918982656 |
|---|---|
| author | Huang, Taoan Ferber, Aaron Tian, Yuandong Dilkina, Bistra Steiner, Benoit |
| author_facet | Huang, Taoan Ferber, Aaron Tian, Yuandong Dilkina, Bistra Steiner, Benoit |
| contents | Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a new one with a contrastive loss. We use graph attention networks and a richer set of features to further improve its performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_01578 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning Huang, Taoan Ferber, Aaron Tian, Yuandong Dilkina, Bistra Steiner, Benoit Artificial Intelligence Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a new one with a contrastive loss. We use graph attention networks and a richer set of features to further improve its performance. |
| title | Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2302.01578 |