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

Shuaixiang ZHANG; Jialin LIU; Hao TONG; Xin YAO

doi:10.1145/3583133.3590739

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 Contributions › Poster › peer-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 language	English
Pages	255-258
Number of pages	4
DOIs	https://doi.org/10.1145/3583133.3590739
Publication status	Published - 15 Jul 2023
Externally published	Yes
Event	Genetic and Evolutionary Computation Conference 2023 - Lisbon, Portugal Duration: 15 Jul 2023 → 19 Jul 2023

Conference

Conference	Genetic and Evolutionary Computation Conference 2023
Abbreviated title	GECCO’23 Companion
Country/Territory	Portugal
City	Lisbon
Period	15/07/23 → 19/07/23

Funding

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

Access to Document

10.1145/3583133.3590739

Cite this

@conference{49166816605c472e89a2f61e92769853,

title = "Generating Competitive Solutions for Uncapacitated Facility Location Problem by Learning from Small Instances",

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{\textquoteright}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. {\textcopyright} 2023 Copyright held by the owner/author(s).",

keywords = "Combinatorial optimization, Experience extract, Facility Location Problem, Meta-heuristic algorithm",

author = "Shuaixiang ZHANG and Jialin LIU and Hao TONG and Xin YAO",

year = "2023",

month = jul,

day = "15",

doi = "10.1145/3583133.3590739",

language = "English",

pages = "255--258",

note = "Genetic and Evolutionary Computation Conference 2023, GECCO{\textquoteright}23 Companion ; Conference date: 15-07-2023 Through 19-07-2023",

}

TY - CONF

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

AU - ZHANG, Shuaixiang

AU - LIU, Jialin

AU - TONG, Hao

AU - YAO, Xin

PY - 2023/7/15

Y1 - 2023/7/15

N2 - 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).

AB - 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).

KW - Combinatorial optimization

KW - Experience extract

KW - Facility Location Problem

KW - Meta-heuristic algorithm

UR - http://www.scopus.com/inward/record.url?scp=85169012229&partnerID=8YFLogxK

U2 - 10.1145/3583133.3590739

DO - 10.1145/3583133.3590739

M3 - Poster

SP - 255

EP - 258

T2 - Genetic and Evolutionary Computation Conference 2023

Y2 - 15 July 2023 through 19 July 2023

ER -

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

Abstract

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this