Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming
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_ | 1866917670325059584 |
|---|---|
| author | Sugimori, Irumi Inoue, Katsumi Nabeshima, Hidetomo Schaub, Torsten Soh, Takehide Tamura, Naoyuki Banbara, Mutsunori |
| author_facet | Sugimori, Irumi Inoue, Katsumi Nabeshima, Hidetomo Schaub, Torsten Soh, Takehide Tamura, Naoyuki Banbara, Mutsunori |
| contents | We propose Large Neighborhood Prioritized Search (LNPS) for solving combinatorial optimization problems in Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. Due to the variability of neighborhoods, LNPS allows for flexible search without strongly depending on the destroy operators. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization. Furthermore, we establish the competitiveness of our LNPS approach by empirically contrasting it to (adaptive) large neighborhood search. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_11305 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming Sugimori, Irumi Inoue, Katsumi Nabeshima, Hidetomo Schaub, Torsten Soh, Takehide Tamura, Naoyuki Banbara, Mutsunori Artificial Intelligence We propose Large Neighborhood Prioritized Search (LNPS) for solving combinatorial optimization problems in Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. Due to the variability of neighborhoods, LNPS allows for flexible search without strongly depending on the destroy operators. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization. Furthermore, we establish the competitiveness of our LNPS approach by empirically contrasting it to (adaptive) large neighborhood search. |
| title | Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2405.11305 |