用于大规模组合优化问题的可并行搜索空间分解方法——基于二次无约束二进制优化

《Scientific Reports》：Parallelizable search-space decomposition for large-scale combinatorial optimization problems using quadratic unconstrained binary optimization

　　

摘要

组合优化问题在工业领域中至关重要。然而，许多这类问题属于NP难问题，其搜索空间会随着问题规模的增加而呈指数级增长，从而导致大规模问题的计算变得不可行。传统的求解器通常将问题视为整体来处理，这使得在结构复杂性增加时效率显著下降。为了解决这一问题，我们提出了一种新的搜索空间分解方法，该方法利用变量之间的内在结构来系统地缩小主问题的规模。我们将变量间的交互成本与单个变量的成本转化为一个受约束的最大割问题，并通过添加惩罚项将其转换为二次无约束二进制优化问题。随后使用伊辛模型求解器快速将问题分解为多个独立的小规模子问题，再利用数学优化求解器对这些子问题进行并行求解。我们在带容量限制的车辆路径问题上验证了该方法。实验结果表明该方法具有三大优势：可行解的生成速度大幅提升，收敛速度加快，1分钟内就能达到传统方法30分钟才能达到的精度，而且问题规模可减少多达95.32%。这些发现表明，搜索空间分解是一种用于高效解决大规模组合优化问题的有效策略。