%0 Journal Article %A GOU Haiwen %A NING Aibing %A HU Qin %A ZHANG Huizhen %T Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem With Penalties %D 2020 %R 10.3778/j.issn.1002-8331.2002-0352 %J Computer Engineering and Applications %P 43-49 %V 56 %N 24 %X

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.

%U http://cea.ceaj.org/EN/10.3778/j.issn.1002-8331.2002-0352