R语言线性和分配/匈牙利法LSAP求解速度优化咨询

当前实现现状 #

• 距离计算环节：采用StatMatch包的gower.dist函数计算高氏距离，该环节耗时极低，不存在性能瓶颈
• 最优匹配求解环节：采用clue包的solve_LSAP函数求解线性和分配问题（LSAP，匈牙利算法实现），由于业务场景需要多次运行该求解器，整体流程耗时过长
• 已验证无效方案：已实测adagio、RcppHungarian两个R包提供的LSAP求解器，运行速度均慢于clue包的原生实现，无法满足提速要求

核心咨询方向 #

目前需要确认两类优化方案的可行性：

• 并行计算改造：是否可通过并行计算实现流程提速，包括对LSAP求解逻辑做局部代码并行改造，改造可参考clue包LSAP源码实现逻辑、LSAP并行求解相关研究成果
• 高性能求解器替换：是否存在性能优于clue包solve_LSAP的其他LSAP求解器可供替换

性能测试基准信息 #

测试所用高氏距离矩阵维度如下：

> dim(gowerdist)
[1]  4309 10366

基准测试的标准调用语句为：

solve_LSAP(gowerdist, maximum = FALSE)

内容的提问来源于stack exchange，提问作者megmac