关键词: 无容量限制设施选址问题, 降阶, 上界, 下界, 回溯算法

Abstract: The uncapacitated facility location problem(UFLP)is a well-known NP-Hard problem in the area of combinatorial optimization, which has wide application value in various fields. The present paper firstly provides new observations of the UFLP model and gives the proof of the new observation. These mathematical properties not only can be used to decide whether some facilities should be open or closed, but also can be used to determine whether some of the connection edges are in service set. Therefore, the size of the original problem can be reduced, and the solution speed can be accelerated by utilizing the new observation in the paper. Given the fact, a new reduction backtracking algorithm based on upper and lower bounds is designed to solve the UFLP. In the end, an example is given to illustrate the principle of the algorithm, and the optimal solution of the example is obtained by utilizing the reduction backtracking algorithm in the paper .Therefore, the results show that the algorithm is feasible and effective.

Key words: uncapacitated facility location problem, reduction, upper bound, lower bound, backtracking algorithm