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

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

The Method for the Inverse Uncapacitated Facility Location Problem Under One Norm

The inverse problem of a general optimization problem is to give a feasible solution by minimizing the change of parameters in the objective function under a fixed norm so that the feasible solution becomes optimal for the original optimization problem after the parameter adjustment. For the uncapacitated facility location problemwhich is NP-hard, we prove that its inverse problem is also NP-hard. In this paper, the classical row generation algorithm is used to calculate the inverse problem of the uncapacitated facility location problem,and then two heuristic methods are developed to get the upper and lower bounds of the inverse problem. These two methods give the upper bound based on the linear relaxation of the subproblem and the lower bound by the local search technique, respectively. The numerical results show that the gap between the upper bound obtained by the linear relaxation method and the optimal value is small, while the efficiency is not improved significantly. However, the gap between the lower bound obtained by the heuristic method and the optimal value is very small, which greatly improves the efficiency of solving the inverse problem.