Efficient Local and Tabu Search Strategies for Large-Scale Quadratic Integer Programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915676837380096 |
|---|---|
| author | Wang, Haibo Alidaee, Bahram |
| author_facet | Wang, Haibo Alidaee, Bahram |
| contents | This study investigates the area of general quadratic integer programming (QIP), encompassing both unconstrained (UQIP) and constrained (CQIP) variants. These NP-hard problems have far-reaching applications, yet the non-convex cases have received limited attention in the literature. To address this gap, we introduce a closed-form formula for single-variable changes, establishing novel necessary and sufficient conditions for 1-Opt local improvement in UQIP and CQIP. We develop a simple local and sophisticated tabu search with an oscillation strategy tailored for large-scale problems. Experimental results on instances with up to 8000 variables demonstrate the efficiency of these strategies, producing high-quality solutions within a short time. Our approaches significantly outperform the Gurobi 11.0.2 solver. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14176 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Local and Tabu Search Strategies for Large-Scale Quadratic Integer Programming Wang, Haibo Alidaee, Bahram Discrete Mathematics Data Structures and Algorithms Optimization and Control This study investigates the area of general quadratic integer programming (QIP), encompassing both unconstrained (UQIP) and constrained (CQIP) variants. These NP-hard problems have far-reaching applications, yet the non-convex cases have received limited attention in the literature. To address this gap, we introduce a closed-form formula for single-variable changes, establishing novel necessary and sufficient conditions for 1-Opt local improvement in UQIP and CQIP. We develop a simple local and sophisticated tabu search with an oscillation strategy tailored for large-scale problems. Experimental results on instances with up to 8000 variables demonstrate the efficiency of these strategies, producing high-quality solutions within a short time. Our approaches significantly outperform the Gurobi 11.0.2 solver. |
| title | Efficient Local and Tabu Search Strategies for Large-Scale Quadratic Integer Programming |
| topic | Discrete Mathematics Data Structures and Algorithms Optimization and Control |
| url | https://arxiv.org/abs/2409.14176 |