Learning-Based Problem Reduction for Large-Scale Uncapacitated Facility Location Problems

The uncapacitated facility location problem (UFLP) is a well-known combinational optimization problem, attracting numerous heuristic and meta-heuristic methods. However, these effective algorithms still encounter challenges when solving large-scale UFLP instances. To deal with the thousands of decision variables, one possible approach is to predict and remove unimportant facilities and thus decreases the dimensionality of problem instances. This paper explores the problem reduction of large-scale instances of UFLP. We propose suitable features of facilities to construct machine learning models for UFLP by learning from small instances. Based on this model, we introduce a novel problem reduction strategy-based optimization framework, and apply it to large instances. Through comprehen-sive experiments, we show that the proposed problem reduction strategy can effectively transform the UFLP instances to smaller ones. The performance of existing solution methods can be significantly enhanced, especially on large-scale instances. Under the proposed framework, we also show the generalization abilities of our models, which can be improved further.