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

Shuaixiang ZHANG, Jialin LIU, Hao TONG, Xin YAO

Research output: Other Conference ContributionsPosterpeer-review

Abstract

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. © 2023 Copyright held by the owner/author(s).
Original languageEnglish
Pages255-258
Number of pages4
DOIs
Publication statusPublished - 15 Jul 2023
Externally publishedYes
EventGenetic and Evolutionary Computation Conference 2023 - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023

Conference

ConferenceGenetic and Evolutionary Computation Conference 2023
Abbreviated titleGECCO’23 Companion
Country/TerritoryPortugal
CityLisbon
Period15/07/2319/07/23

Bibliographical note

This work was supported by the National Natural Science Foundation of China (Grants No. 62250710682, 61906083), the Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386), the Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531), the Shenzhen Fundamental Research Program (Grant No. JCYJ20190809121403553), and the Research Institute of Trustworthy Autonomous Systems.

Keywords

  • Combinatorial optimization
  • Experience extract
  • Facility Location Problem
  • Meta-heuristic algorithm

Fingerprint

Dive into the research topics of 'Generating Competitive Solutions for Uncapacitated Facility Location Problem by Learning from Small Instances'. Together they form a unique fingerprint.

Cite this