2024/09/21 by Haibo Wang, Wang, Haibo, Bahram Alidaee +1
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2409.14176
openalex publication_date 2024/09/21 · openalex created_date 2024/10/26 · openalex updated_date 2026/07/28
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.