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

Genetic and Evolutionary Computation Conference (GECCO)

PROCEEDINGS OF THE 2023 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE COMPANION, GECCO 2023 COMPANION

JUL 15-19, 2023

null,Lisbon,PORTUGAL

1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES

ASSOC COMPUTING MACHINERY

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.

Facility Location Problem Experience extract Meta-heuristic algorithm Combinatorial optimization

第一 ; 通讯

英语

EI ; CPCI-S

National Natural Science Foundation of China["62250710682","61906083"]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems

WOS:001117972600086

Web of Science

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]. 1601 Broadway, 10th Floor, NEW YORK, NY, UNITED STATES:ASSOC COMPUTING MACHINERY,2023.