提出新局部搜索算法，高效求解带二次项的整数规划问题
Local Search for Integer Quadratic Programming
- 设计四种新算子，可处理目标函数和约束中的二次项
- 在QPLIB和MINLPLIB上表现媲美商业求解器Gurobi
- 在6个公开实例上刷新最优记录，适合求解复杂整数规划
整数二次规划（IQP）是运筹学中的重要问题。尽管局部搜索是解决困难问题的强大方法，但针对IQP的局部搜索算法研究仍处于初期阶段。本文提出一种高效的局部搜索求解器LS-IQCQP，专为求解通用IQP而设计。提出四种新的局部搜索算子，能够处理目标函数、约束条件或两者中的二次项。此外，引入双模式局部搜索算法，结合新设计的评分函数以提升搜索效率。在标准IQP基准测试集QPLIB和MINLPLIB上，将LS-IQCQP与多个最先进求解器进行对比。实验结果表明，LS-IQCQP在性能上可与最强的商业求解器Gurobi相媲美，并优于其他先进求解器。此外，该算法在QPLIB和MINLPLIB的开放实例中建立了6项新纪录。
原文摘要 · Abstract (English)
Integer Quadratic Programming (IQP) is an important problem in operations research. Local search is a powerful method for solving hard problems, but the research on local search algorithms for IQP solving is still on its early stage. This paper develops an efficient local search solver for solving general IQP, called LS-IQCQP. We propose four new local search operators for IQP that can handle quadratic terms in the objective function, constraints or both. Furthermore, a two-mode local search algorithm is introduced, utilizing newly designed scoring functions to enhance the search process. Experiments are conducted on standard IQP benchmarks QPLIB and MINLPLIB, comparing LS-IQCQP with several state-of-the-art IQP solvers. Experimental results demonstrate that LS-IQCQP is competitive with the most powerful commercial solver Gurobi and outperforms other state-of-the-art solvers. Moreover, LS-IQCQP has established 6 new records for QPLIB and MINLPLIB open instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。