End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location

2025-05-06 0 0 924.49KB 14 页 10玖币

侵权投诉

End-to-End Pareto Set Prediction with Graph

Neural Networks for Multi-objective Facility

Location

Shiqing Liu1, Xueming Yan∗2,1, and Yaochu Jin∗1

1Faculty of Technology, Bielefeld University, 33619 Bielefeld, Germany

2School of Information Science and Technology, Guangdong University of Foreign

Studies, Guangzhou 510000, China

yanxm@gdufs.edu.cn;yaochu.jin@uni-bielefeld.de

Abstract. The facility location problems (FLPs) are a typical class of

NP-hard combinatorial optimization problems, which are widely seen in

the supply chain and logistics. Many mathematical and heuristic algo-

rithms have been developed for optimizing the FLP. In addition to the

transportation cost, there are usually multiple conﬂicting objectives in

realistic applications. It is therefore desirable to design algorithms that

ﬁnd a set of Pareto solutions eﬃciently without enormous search cost.

In this paper, we consider the multi-objective facility location problem

(MO-FLP) that simultaneously minimizes the overall cost and maxi-

mizes the system reliability. We develop a learning-based approach to

predicting the distribution probability of the entire Pareto set for a given

problem. To this end, the MO-FLP is modeled as a bipartite graph op-

timization problem and two graph neural networks are constructed to

learn the implicit graph representation on nodes and edges. The network

outputs are then converted into the probability distribution of the Pareto

set, from which a set of non-dominated solutions can be sampled non-

autoregressively. Experimental results on MO-FLP instances of diﬀerent

scales show that the proposed approach achieves a comparable perfor-

mance to a widely used multi-objective evolutionary algorithm in terms

of the solution quality while signiﬁcantly reducing the computational

cost for search.

Keywords: Combinatorial optimization ·Multi-objective optimization

·Graph neural network.

1 Introduction

Multi-objective combinatorial optimization (MOCO) has received considerable

attention over the past few decades due to its wide applications in the real-

world. In MOCO, there are multiple conﬂicting objectives, and it is often non-

trivial to optimize them simultaneously [1]. The multi-objective facility location

problem (MO-FLP) is a typical NP-hard MOCO problem. It aims to determine

an optimal set of facility locations that can satisfy all the customer demands

within certain constraints, while minimizing the total costs and maximizing the

arXiv:2210.15220v1 [cs.LG] 27 Oct 2022

2 S. Liu et al.

system reliability. Decisions made in facility location have a long-term impact

on numerous operational and logistical strategies and are critical to both private

and public ﬁrms [14].

A lot of work has been devoted to developing mathematical methods or hand-

crafted heuristic algorithms for solving MOCO problems. An intuitive approach

is to reduce a multi-objective problem to a single-objective problem by calcu-

lating the weighted sum of multiple objectives. However, assigning a suitable

weight to each objective introduces an additional hyperparameter optimization

problem. Evolutionary algorithms (EAs) have been successful in approximat-

ing the Pareto set of MOCOs by maintaining and updating a set of solutions

[7,34,6]. However, EAs and other population-based methods often require a large

number of function evaluations during the search process, incurring prohibitive

computing overhead when the objective functions are expensive to evaluate [17].

Moreover, it is diﬃcult to resue the knowledge about the optimal sets of solutions

for other instances of the same problem that have already been solved.

Most existing work considers MOCO as constrained mixed-integer linear pro-

gramming, overlooking the highly structured nature of the combinatorial op-

timisation problems. For example in the facility location problem (FLP), the

locations of all facilities and customers can be represented by a set of nodes

separately, and the transport overhead is the weight of the edge connecting two

nodes from diﬀerent sets. Generally, permutation-based COPs can be formulated

as sequential decision-making tasks on graphs [18], and matching-based COPs

can be considered as node and edge classiﬁcation or prediction tasks on graphs.

Therefore, machine learning methods can be used to extract high-dimensional

characteristics of the graph-based problems and learn optimal policies to solve

COPs instead of relying on handcrafted heuristics [1,31]. Graph neural networks

(GNNs) can exploit the message passing scheme to learn the structural informa-

tion of nodes and edges eﬃciently according to the graph topology. Consequently,

GNNs are well-suited for tackling the MOCO problems [16,11,4]. However, most

existing methods focus on solving permutation-based problems and only consider

one single objective, neglecting the study of more commonly seen matching-based

multi-objective COPs [9].

In this paper, we propose a learning-based approach leveraging graph con-

volutional networks (GCNs) to approximate the Pareto set distribution of the

multi-objective facility location problem. The overall framework is shown in

Fig. 1. The problem is formulated as a bipartite graph with edge connections be-

tween two independent sets of nodes. The model consists of two diﬀerent residual

gated GCNs for node classiﬁcation and edge prediction tasks, respectively. The

model takes bipartite graphs as the input, and transforms the original node and

edge features into high-dimensional embeddings. Several residual gated graph

convolutional layers are used to learn the structural information from the graph

topology and update the embeddings iteratively. The output of the ﬁrst GCN is a

prediction of the probability of each factory being selected in the Pareto optimal

solutions. The output of the second GCN is a probabilistic model in the form of

an adjacency matrix, denoting the probability of each customer being assigned

to each selected factory. The output probability models can be sampled directly

to generate a set of Pareto solutions in a one-shot manner. The two networks are

End-to-End Pareto Set Prediction with Graph Neural Networks 3

Input Bipartite Graph

GCNnode

GCNedge

P(X)

Pareto Front

P(Y)

Facilities

Customers

Fig. 1: An overview of the proposed approach. The MO-FLP instance is con-

verted into a bipartite graph as the input to the GCNs. The two GCN mod-

els perform node classiﬁcation and edge prediction and output the probability

models, which are co-sampled to generate a set of non-dominated solutions in a

one-shot manner.

trained coordinately by supervised learning. The training data is a large set of

MO-FLP instances with various Pareto optimal solutions generated by a multi-

objective evolutionary algorithms, e.g., the fast elitism non-dominated sorting

genetic algorithm (NSGA-II) [7]. The main contributions of this paper include:

1. We formulate the MO-FLP as a bipartite graph optimization task and de-

velop a novel learning-based combinatorial optimization method to directly

approximate the Pareto set of new instances of the same problem without

extra search.

2. We propose an end-to-end probabilistic prediction model based on two GCNs

for node and edge predictions, respectively, and train the model with a su-

pervised learning using data generated by a multi-objective evolutionary

algorithm.

3. We demonstrate the eﬃciency of our proposed method for solving MO-

FLP instances with diﬀerent scales. Our experimental results show that

the learning-based approach can approximate a set of Pareto optimal so-

lutions without additional search, signiﬁcantly reducing the computational

cost compared to population-based algorithms.

2 Related Work

2.1 Facility Location Problem

FLPs are a typical class of NP-hard combinatorial problems in operations re-

search [23]. FLPs consider choosing an optimal set of facilities among all the

potential sites and determines an allocation scheme for all customers, under the

constraints that all customer demands must be satisﬁed by the constructed facil-

ities. A common objective of FLPs is to minimize the total costs, which consist

of the transportation cost and the ﬁxed cost.

FLPs have several variants depending on diﬀerent constraint settings and

objective functions. Each candidate facility may have a limited or unlimited

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

End-to-EndParetoSetPredictionwithGraphNeuralNetworksforMulti-objectiveFacilityLocationShiqingLiu1,XuemingYan2;1,andYaochuJin11FacultyofTechnology,BielefeldUniversity,33619Bielefeld,Germany2SchoolofInformationScienceandTechnology,GuangdongUniversityofForeignStudies,Guangzhou510000,Chinayanxm@gdufs....

展开>> 收起<<

End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location.pdf

共14页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: