Fast Local Search Strategies for Large-Scale General Quadratic Integer Programming
<|reference_start|>Fast Local Search Strategies for Large-Scale General Quadratic Integer Programming: 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.<|reference_end|>
@article{wang2024fast,
    title={Fast Local Search Strategies for Large-Scale General Quadratic Integer
  Programming},
    author={Haibo Wang and Bahram Alidaee},
    journal={arXiv preprint arXiv:2409.14176},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.14176},
    primaryClass={cs.DM cs.DS math.OC}
}