L1范数下无容量限制设施选址逆问题的求解方法

DOI码：

10.12005/orms.2022.0220

发表刊物：

运筹与管理

关键字：

无容量限制设施选址问题, 逆问题, 行生成算法, 启发式算法

摘要：

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。

合写作者：

刘林冬,于成成

第一作者：

李子慷

论文编号：

[12]

卷号：

31

期号：

7

页面范围：

86-92

是否译文：

否

发表时间：

2022-08-17