.png){kind=icon}
返回
Local Search for Integer Quadratic Programming
.png){kind=icon}
PRE
AI
DOI：10.1287/ijoc.2025.1178.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
整数二次规划（IQP）是运筹学中的一个重要问题。局部搜索是求解困难问题的一种强大的原始启发式方法，但针对IQP的局部搜索算法研究仍处于早期阶段。本文介绍了一种高效的局部搜索算法LS-IQCQP，其代表“用于整数二次约束二次规划的局部搜索”。该算法旨在求解一般的IQP问题，能够处理目标函数、约束条件或两者中包含二次项的情况。我们提出了四种新设计的算子：用于可行性的根算子，以及用于优化目标函数的不等式探索、等式平衡和自由无约束算子。为评估这些算子的质量，引入了加权评分函数。基于评分函数，LS-IQCQP迭代应用有效算子，并采用类似WalkSAT的方法（一种用于可满足性问题的经典局部搜索算法），通过随机选择算子以跳出局部最优。实验在来自二次规划库（QPLIB）和混合整数非线性规划库（MINLPLIB）的标准IQP基准上进行，将LS-IQCQP与几种最先进的IQP求解器进行比较。实验结果表明，在快速找到良好可行解方面，LS-IQCQP与最强大的商业求解器Gurobi及其他最先进的求解器具有竞争力。此外，LS-IQCQP通过找到新的最优已知解，为QPLIB和MINLPLIB开放实例建立了六项新纪录。
Keyword:
integer quadratic programming
local search
primal heuristic
期刊
I
IF:
2.1
论文数:
90
被引数:
3.2K
.png){kind=icon}
查看更多内容