Abstract:

The Uncapacitated Facility Location Problem（UFLP） is a classical NP-Hard problem in the area of combinatorial optimization. Aiming at the Uncapacitated Facility Location Problem With Penalties（UFLPWP）, this paper researches the new observations of UFLWP and proves the new observations, which including the properties that can determine batches of facilities that must engage. A backtracking algorithm with upper and lower bounds based on these mathematical properties is designed to decrease the scale and the degree of complexity of the original problem and solve the UFLPWP. An example is illustrated to illuminate the principle further.

Key words: Uncapacitated Facility Location Problem With Penalties（UFLPWP）, reduction, upper bound, lower bound, backtracking algorithm

摘要：

无容量设施选址问题（Uncapacitated Facility Location Problem，UFLP）是组合优化中经典的NP-Hard问题之一。针对UFLP的变形问题之一，即带惩罚的无容量设施选址问题（Uncapacitated Facility Location Problem With Penalties，UFLPWP），研究了UFLPWP的数学性质，其中包括可以批量确定某些设施一定关闭的性质，并进行了数学证明，利用这些数学性质可以对问题进行降阶，进而缩小问题的规模。在此基础上设计了基于上、下界的回溯算法来求解UFLPWP。通过一个示例分析，进一步阐述该算法的原理。

关键词: 带惩罚的无容量设施选址问题, 降阶, 上界, 下界, 回溯算法