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

Shuaixiang Zhang1; Yixuan Yang1; Hao Tong1; Xin Yao1,2

10.1109/CEC60901.2024.10611785

2024-07-05

979-8-3503-0837-2

2024 IEEE Congress on Evolutionary Computation (CEC)

30 June-5 July 2024

Yokohama, Japan

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.

第一

EI

1.Department of Computer Science and Engineering, Guangdong Provincial Key Laboratory of Brain-inspired Intelligent Computation, Southern University of Science and Technology, Shenzhen, China
2.Department of Computing and Decision Sciences, Lingnan University, Hong Kong SAR, China

Shuaixiang Zhang,Yixuan Yang,Hao Tong,et al. Learning-Based Problem Reduction for Large-Scale Uncapacitated Facility Location Problems[C],2024.