Scholarlink

<p>This study investigates the area of general quadratic integer programming (QIP), encompassing both unconstrained (UQIP) and multi-constrained (CQIP) variants. These NP-hard problems have far-reaching applications, yet 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-<i>Opt</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Efficient local and tabu search strategies for large-scale general quadratic integer programming

  • 期刊论文

  • 发表日期：

    2026年3月7日

查看全文
  • Haibo Wang,
  • Bahram Alidaee

摘要

This study investigates the area of general quadratic integer programming (QIP), encompassing both unconstrained (UQIP) and multi-constrained (CQIP) variants. These NP-hard problems have far-reaching applications, yet 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.