Generating Competitive Solutions for Uncapacitated Facility Location Problem by Learning from Small Instances

Zhang，Shuaixiang; Liu，Jialin; Tong，Hao; Yao，Xin

10.1145/3583133.3590739

2023-07-15

GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion

255-258

The uncapacitated facility location problem (UFLP) is an NP-hard problem with a wide range of applications. It aims to choose a set of facilities to serve customers with the lowest total cost. This paper explores the idea of learning good heuristics, which could be regarded as a kind of optimization experiences, over a set of small problem instances. Then the learned heuristics (i.e., gained experiences) are used to generate good solutions for large-scale UFLPs although the large-scale ones are never used during learning. In this paper, we propose a novel facility opening estimation (FOE) heuristic for UFLP. Each facility’s opening probability is estimated by a model related to its local apportioned cost (LAC). The model learns from the experience extracted in solving small UFLPs. Then, the model is embedded into the FOE heuristic to generate solutions for large UFLPs. The empirical results and analysis demonstrate that the optimization experience extraction is effective and can assist in generating high-quality solutions for large UFLPs.

Combinatorial optimization Experience extract Facility Location Problem Meta-heuristic algorithm

First ; Corresponding

English

2-s2.0-85169012229

Scopus

Southern University of Science and Technology,Shenzhen,China

Zhang，Shuaixiang,Liu，Jialin,Tong，Hao,et al. Generating Competitive Solutions for Uncapacitated Facility Location Problem by Learning from Small Instances[C],2023:255-258.