The State-of-the-Art Survey on Optimization Methods for Cyber-physical Networks

2025-05-06 0 0 966.82KB 33 页 10玖币

侵权投诉

The State-of-the-Art Survey on Optimization Methods for

Cyber-physical Networks

Babak Aslania,Shima Mohebbia,∗and Edward J. Oughtonb

aDepartment of Systems Engineering and Operations Research, George Mason University, Fairfax, VA

bDepartment of Geography and Geoinformation Science, George Mason University, Fairfax, VA

ARTICLE INFO

Keywords:

Cyber-physical Systems

Restoration planning

Mathematical modeling

Optimization

Scalability

ABSTRACT

Cyber-Physical Systems (CPS) are increasingly complex and frequently integrated into modern

societies via critical infrastructure systems, products, and services. Consequently, there is a need

for reliable functionality of these complex systems under various scenarios, from physical fail-

ures due to aging, through to cyber attacks. Indeed, the development of eﬀective strategies to

restore disrupted infrastructure systems continues to be a major challenge. Hitherto, there have

been an increasing number of papers evaluating cyber-physical infrastructures, yet a compre-

hensive review focusing on mathematical modeling and diﬀerent optimization methods is still

lacking. Thus, this review paper appraises the literature on optimization techniques for CPS fac-

ing disruption, to synthesize key ﬁndings on the current methods in this domain. A total of 108

relevant research papers are reviewed following an extensive assessment of all major scientiﬁc

databases. The main mathematical modeling practices and optimization methods are identi-

ﬁed for both deterministic and stochastic formulations, categorizing them based on the solution

approach (exact, heuristic, meta-heuristic), objective function, and network size. We also per-

form keyword clustering and bibliographic coupling analyses to summarize the current research

trends. Future research needs in terms of the scalability of optimization algorithms are discussed.

Overall, there is a need to shift towards more scalable optimization solution algorithms, empow-

ered by data-driven methods and machine learning, to provide reliable decision-support systems

for decision-makers and practitioners.

1. Introduction

Cyber-physical systems (CPS) integrate computation, communication, sensor, and network technologies equipped

with feedback loops for managing interdependency among their physical and cyber components (Gürdür and Asplund,

2018;Tu et al.,2019). Indeed, the modern networked world in which we live has made it possible to have near-

ubiquitous information at hand, leading to the increased embedding of this information into CPS approaches (Jazdi,

2014). CPS have emerged by integrating Information and Communication Technology with Critical Infrastructures

such as water, energy, and transportation systems, leading to increased complexity (Oughton et al.,2018). In speciﬁc,

water infrastructure includes physical elements (pipeline, pump stations, detention basins, treatment facilities), cyber

elements (SCADA systems). Similarly, transportation infrastructures entail physical (roads, railways), cyber (traﬃc

control technologies and sensors) elements Samih (2019). Although this novel integration enhances the eﬃciency and

service level of CPS, it also signiﬁcantly increases the connections among system components and the interdependen-

cies between diﬀerent sectors of CPS such as the cyber-physical-social interdependency between water, transportation,

and cyber infrastructure systems (Mohebbi et al.,2020).

Nowadays, CPS are ubiquitous, with diﬀerent functionalities and capabilities, often supporting critical missions

that have signiﬁcant economic and societal importance. The emerging CPS, such as smart cities, autonomous vehicles,

and modern transportation systems are expected to be highly intelligent, electriﬁed, and connected (Broo et al.,2021).

Indeed, major trends in new wireless technologies (e.g., 5G/6G) focus on enabling wide-area connectivity for remote

control of previously unconnected assets (Oughton and Lehr,2022). Thus, this trend will have signiﬁcant ramiﬁcations

for CPS. While there are many deﬁnitions of what constitutes critical infrastructures, the United States has a sixteen-

sector deﬁnition ranging from ﬁnancial services to the defence industrial base (DHS,2021).

In recent decades, the CPS around the world experienced disastrous situations, such as Hurricane Katrina in 2005,

the earthquakes in Japan in 2011, and Hurricanes Harvey, Irma, and Maria in 2017, all of which profoundly impacted

baslani@gmu.edu (B. Aslani); smohebbi@gmu.edu (S. Mohebbi); eoughton@gmu.edu (E.J. Oughton)

ORCID(s): 0000-0002-2734-9398 (B. Aslani); 0000-0002-1587-0506 (S. Mohebbi); 0000-0002-2766-008X (E.J. Oughton)

Aslani et al.: Preprint submitted to Elsevier Page 1 of 33

arXiv:2210.03642v1 [math.OC] 7 Oct 2022

Survey on Optimization Methods for Cyber-physical Networks

the economic growth, social development, and public safety (Mohebbi et al.,2020). For instance, Hurricane Irma

caused a widespread power outage to customers in Florida, and Hurricane Harvey triggered a signiﬁcant disruption

in the transportation system of Houston, Texas (Rahimi-Golkhandan et al.,2022). Given the presence of such threats

to CPS, decision-makers seek to have decision-making tools (both quantitative and qualitative) to protect the standard

functionality of such systems in dealing with disruptions (Aslani and Mohebbi,2022). In particular, researchers have

attempted to utilize optimization methods for proactive and restoration decisions among CPS.

The development of state-of-the-art commercial solvers, such as Gurobi and CPLEX, and the interpretability of

results could be mentioned as main drivers for the increasing trend of optimization algorithms in this application area.

Even though some review papers focus on the solution approaches and interdependencies among CPS (e.g., Ouyang

(2014) and Mohebbi et al. (2020)), a systematic evaluation of mathematical models and optimization methods devel-

oped in the context of CPS is absent in the literature. In addition, the previous reviews mainly focus on interdependent

networks, while a signiﬁcant share of related studies investigate standalone infrastructure systems. Therefore, a com-

prehensive analysis of optimization methods for CPS will provide insightful directions for future research in theory

and application.

We devised a comprehensive strategy in this study to identify the main trends in the literature and pinpoint the gaps

worthy of investigation in future works. In the mathematical modeling aspect, we attempted to decompose the models

based on essential elements such as objective function, decision variables, and constraints to summarize a large body

of information in an interpretable format. On the other hand, we separated the literature for deterministic and stochastic

models to analyze the optimization-based solution algorithms for each class regarding their speciﬁc features. We also

thoroughly investigated the scale of CPS networks and failure types to highlight the missing conceptual assumptions

in the literature. The complementary element of our analysis is the bibliographic analysis to explore the link between

methodology-based and application-based keywords, publication outlets, and how these two aspects are interconnected

in practice.

The main contribution of this paper is providing a comprehensive review of optimization methods and mathematical

modeling for CPS. We explored all major databases prudently to select the most reliable pool of papers based on the

scope and methodology. The result of the search process, 108 articles, has been organized and analyzed based on

the formulation type, optimization solution approach, modeling elements, network size, and failure types. The review

focuses on the studies developing mathematical models and applying an optimization method to solve the underlying

problem. In addition, we utilize a holistic approach to relate the solution algorithm design, CPS network features, and

conceptual/modeling practices to provide insights into developing practical decision support systems with enriched

optimization frameworks for city-scale CPS.

The remainder of the paper is structured as follows: In section 2, we present the deﬁnition of fundamental concepts

and technical terms. Next, section 3explains the search process and selection criteria to establish the pool of literature

to be reviewed. In section 4, we categorize the selected studies based on multiple criteria. Additionally, section 5

includes detailed solution methods and mathematical modeling analyses. Finally, the discussion and future research

directions are provided in section 6.

2. Deﬁnition of Concepts and Assumptions

2.1. Mathematical Modeling

Mathematical modelling is the art of capturing and describing a real-world problem in the form of mathematical

terms, usually in the form of equations, and then using these equations both to help understand the original problem,

and also to discover new features about the problem. The modeling process can be construed as an iterative process

in which real-life problems are translated into mathematical language, solved within a symbolic system, and the solu-

tions is implemented within the real-life problem environment. Mathematical modeling aims to capture the essential

characteristics of a complex real-life problem and transform them into a more abstract representation (Keller,2017).

In this work, we focus on optimization problems where the objective function(s) and constraints for a system can be

expressed by linear or non-linear functions in the form of standard mathematical models.

2.1.1. Deterministic Models

In a deterministic mathematical model, it is assumed that a set of all variable states is uniquely determined by

parameters in the model and by sets of previous states of these variables. In other words, the parameters and variables

of the system are fully known and invariable over the optimization horizon. The general form of a deterministic model

Aslani et al.: Preprint submitted to Elsevier Page 2 of 33

Survey on Optimization Methods for Cyber-physical Networks

will be as follows:











𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓 (𝑥) = 𝑐1𝑥1+... +𝑐𝑛𝑥𝑛

subject to ∶𝑎(𝑥𝑖)≥𝑏𝑖, 𝑖 = 1,2, ..., 𝑝

𝑥𝑖≥0, 𝑗 = 1,2, ..., 𝑛

𝑐∈𝐶, 𝑎 ∈𝐴, 𝑏 ∈𝐵, 𝑥 ∈𝑋

(1)

Where the information about tuple 𝐴𝐵𝐶is fully known prior to the optimization and assumes to be unvarying

over the time horizon.

•Single-objective Models: A single-objective optimization problem refers to a problem where a number of deci-

sion variables 𝑥𝑖are deﬁned to minimize (or maximize) one desired objective function 𝑓over a set of constraints

𝐶.

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒

𝑥{𝑓(𝑥)subject to 𝑥∈𝑋 ⊆ ℝ𝑛}(2)

where 𝑋is the feasible set of solutions for the optimization problem.

We can deﬁne the single-objective optimization problem with both equality and inequality set of constraints.

Formally, a minimization problem, with 𝑝inequality constraints and 𝑚equality constraints is represented by:











𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓 (𝑥)

subject to ∶𝑔𝑖(𝑥)≥0, 𝑖 = 1,2, ..., 𝑝

ℎ𝑗(𝑥)=0, 𝑗 = 1,2, ..., 𝑚

𝑥∈𝑋 ⊆ ℝ𝑛

(3)

•Multi-objective Models: Optimization problems in practice can include several conﬂicting objectives to mini-

mize or maximize simultaneously. A general continuous multi-objective problem aims to ﬁnd 𝑛decision vari-

ables 𝑥∈ℝ𝑛that simultaneously minimize (or maximize) 𝑘objective functions such as 𝑓𝑟∶ℝ𝑛⟼ℝ, 𝑟 =

1, . . . , 𝑘 (Kadziński et al.,2017). Similar to single-objective models, the decision variables and objectives are

subject to a set of bounds and constraints. A feasible solution to the Multi-Objective Optimization problem

satisﬁes all the bounds for a decision variable, together with the 𝑝and 𝑚inequalities and equality constraints.

The standard form of a multi-objective optimization problem will be as follows:











𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑓 (𝑥, 𝑝)≡(𝑓1(𝑥), 𝑓2(𝑥), ...𝑓𝑘(𝑥))

subject to ∶ℎ𝑖(𝑥)=0, 𝑖 = 1,2, ..., 𝑚

𝑔𝑗(𝑥)≥0, 𝑖 = 1,2, ..., 𝑝

𝑥𝑙∈ [𝑥𝐿

𝑙, 𝑥𝑈

𝑙], 𝑙 = 1,2, ..., 𝑛

(4)

2.1.2. Stochastic Models

The underlying assumption in stochastic models is the presence of uncertainty in the parameters and decision

variables of the model. In other words, the variable and parameter states are not unique values but rather are presented

in the form of probability distributions. Let 𝑋be the domain of all feasible decisions and 𝑥a speciﬁc decision. The

optimization goal is to search over 𝑋to ﬁnd a decision that minimizes (or maximizes) an 𝐹function. Let 𝜉denote

random information available only after the decision is made. In the general form of stochastic modeling, we deﬁne the

objective function as a random cost function such as 𝐹(𝑥, 𝜉)and constraints can also be written as random function.

Aslani et al.: Preprint submitted to Elsevier Page 3 of 33

Survey on Optimization Methods for Cyber-physical Networks

Since 𝐹(𝑥, 𝜉)cannot be optimized directly, the focus will be on the expected value, 𝔼[𝐹(𝑥, 𝜉)]. The general form of a

stochastic optimization problem can be presented as follows (Hannah,2015):

𝜁∗=𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒

𝑥∈𝑋{𝑓(𝑥) = 𝔼[𝐹(𝑥, 𝜉)]} (5)

Where the optimal solution will be the set of 𝑆∗= {𝑥∈𝑋∶𝑓(𝑥) = 𝜁∗}.

•Two-stage stochastic models: Two-stage stochastic mathematical model is the most common formulation in the

ﬁeld of stochastic programming. The basic idea of this modeling approach is that optimal decisions should be

based on data available at the time the decisions are made and cannot depend on future observations. A general

two-stage stochastic programming problem is given by (Shapiro and Philpott,2007):

min

𝑥∈ℝ𝑛𝑔(𝑥) = 𝑐𝑇𝑥+𝐸𝜉[𝑄(𝑥, 𝜉)]

subject to 𝐴𝑥 =𝑏

𝑥≥0

(6)

where 𝑄(𝑥, 𝜉)is the optimal value of the second-stage problem given below:

min

𝑦{𝑞(𝑦, 𝜉)𝑇(𝜉)𝑥+𝑊(𝜉)𝑦=ℎ(𝜉)}.(7)

In such formulation, 𝑥∈ℝ𝑛is the ﬁrst-stage decision variable vector, 𝑦∈ℝ𝑚is the second-stage decision

variable vector, and 𝜉(𝑞, 𝑇 , 𝑊 , ℎ)contains the data of the second-stage problem. In the ﬁrst stage, we have to

make a "here-and-now" decision 𝑥before the realization of the uncertain data 𝜉, viewed as a random vector, is

known. In the second stage, after a realization of 𝜉becomes available, we optimize the decisions by solving

a new optimization problem updated with the new information. The general case of a two-stage problem is

linear with linear terms for objective function and the constraint. However, conceptually this is not essential,

and integer or nonlinear assumptions could also be incorporated into two-stage models (Pichler and Tomasgard,

2016).

•Multi-stage stochastic models: This stochastic formulation has been introduced as a generalization of two-stage

models to capture the sequential realization of uncertainties and labelled as multistage stochastic programming.

In this setting, the time horizon is discretized into “stages” where each stage has the realizations of uncertainties

at the current stage. A wide range of complex and dynamic optimization problems are eﬀectively modeled as

multi-stage stochastic programs, possessing key decision variables in one or more of the stages. In the multi-

stage setting, the uncertainty of the problem is revealed sequentially in 𝑇stages. The random variable 𝜉is split

into 𝑇− 1 chunks, 𝜉= (𝜉1, ..., 𝜉𝑇−1), and the problem at hand is to decide at each stage 𝑡= 1, ..., 𝑇 what is the

optimal action, 𝑥𝑡(𝜉[1,𝑡−1]), given the previous observations 𝜉[1,𝑡−1] ∶= (𝜉1, ..., 𝜉𝑡−1). The global variable of this

problem can be written as follows (Bakker et al.,2020):

𝑥(𝜉)=(𝑥1, 𝑥2(𝜉1),…, 𝑥𝑇(𝜉[1,𝑇 −1])) ∈ ℝ𝑛1×⋯×ℝ𝑛𝑇(8)

where (𝑛1, ..., 𝑛𝑇)are the size of the decision variable at each stage and 𝑛=

𝑇



𝑡=1

𝑛𝑡is the total size of the problem.

•Markov Decision Process (MDP): MDP is a mathematical framework for sequential decision making under un-

certainty that has informed decision making in a discrete-time stochastic environment. This branch of stochastic

programming has been adopted in a variety of application areas including inventory control, scheduling, and

medicine (Steimle et al.,2021).

A Markov decision process is formulated in the form of a tuple such as 𝑆, 𝐴, 𝑃𝑎, 𝑅𝑎, where:

Aslani et al.: Preprint submitted to Elsevier Page 4 of 33

Survey on Optimization Methods for Cyber-physical Networks

–𝑆is a set of states or the state space.

–𝐴is a set of actions or the action space.

–𝑃𝑎(𝑠, 𝑠′) = Pr(𝑠𝑡+1 =𝑠′∣𝑠𝑡=𝑠, 𝑎𝑡=𝑎)is the probability that action 𝑎in state 𝑠at time 𝑡will lead to state

𝑠′at time 𝑡+ 1.

–𝑅𝑎(𝑠, 𝑠′)is the immediate reward (or expected immediate reward) received after transitioning from state 𝑠

to state 𝑠′, due to action 𝑎.

A policy function 𝜋is a probabilistic mapping from state space (𝑆) to action space (𝐴).

At each time step, the process is in some state 𝑠, and the decision-maker may choose any action 𝑎that is available

in state 𝑠. The process responds at the next time step by randomly moving into a new state 𝑠′, and giving the

decision-maker a corresponding reward 𝑅𝑎(𝑠, 𝑠′). The probability that the process moves into its new state 𝑠′

is inﬂuenced by the chosen action; however, it is independent of all previous states and actions to satisfy the

Markov property.

The goal of a Markov decision process is to ﬁnd an optimal policy for the decision-maker: a function 𝜋that

speciﬁes the action 𝜋(𝑠)that the decision-maker will choose when in state 𝑠. The objective of a general MDP is

to choose a policy 𝜋that will maximize some cumulative function of the random rewards over a inﬁnite horizon:

max(𝑍) = 𝐸∞



𝑡=0

𝛾𝑡𝑅𝑎𝑡(𝑠𝑡, 𝑠𝑡+1)(9)

Where 𝑎𝑡=𝜋(𝑠𝑡)is the selected actions given by the policy, and the expectation is taken over 𝑠𝑡+1 ∼𝑃𝑎𝑡(𝑠𝑡, 𝑠𝑡+1).

In this equation, 𝛾is a discount factor satisfying 0≤𝛾≤1, which is usually close to 1.

2.2. Optimization Solution Algorithms

Global optimization algorithms can be broadly divided into three groups including exact methods (e.g., branch-and-

bound, cutting planes, and decomposition) and heuristic methods, and evolutionary methods (e.g., Genetic Algorithm

(GA)). The main diﬀerence in these classes originates in the search process and the optimality guarantee. In other

words, while in the exact methods can provide solution with guaranteed optimality, there is no certainty about the

optimal status of the output for heuristic and evolutionary methods.

•Exact methods: Exact methods can comb the solution space of any optimization problem to ﬁnd the optimal so-

lution among all candidate feasible solutions. This guaranteed optimality is the primary rationale for implement-

ing these approaches for diﬀerent classes of optimization problems. An exact optimization method is essentially

a solution method of choice that can solve an optimization problem with an eﬀort that grows polynomially with

the problem size. The most common classes are branch-and-bound, cutting plane, and decomposition methods.

•Heuristic methods Approximation algorithms are a diverse family of solution methods for optimization prob-

lems that return an approximate solution without any promise of optimality. Speciﬁcally, heuristics solution

methods are problem-speciﬁc approximate algorithms attempting to exploit the underlying rules of the problem

at hand to obtain a high-quality solution. Even though heuristics do not guarantee to ﬁnd an optimal solution,

they are simple and much faster than exact approaches. There are two diﬀerent types of heuristics: Construction

heuristics, which construct one solution from scratch by performing iterative construction steps, and Improve-

ment heuristics, which start with a complete solution and iteratively apply problem-speciﬁc search operators

to search the solution space. Among the well-known heuristics, nearest neighbor heuristic, cheapest insertion

heuristic, and k-opt heuristic are noteworthy that are developed for Travelling Salesman Problem (TSP) problem

but are applicable to other optimization problems as well (Rothlauf,2011)

•Evolutionary methods Evolutionary algorithms (or interchangeably Meta-heuristics) are computationally ef-

ﬁcient methods for solving complex optimization problems approximately, particularly for the Combinatorial

Optimization Problems class of optimization problems with discrete decision variables and ﬁnite search space.

Since these methods can provide near-optimal solutions in reasonable computational time for NP-Hard class

Aslani et al.: Preprint submitted to Elsevier Page 5 of 33

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

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

10 玖币 0人已下载

立即下载

摘要：

TheState-of-the-ArtSurveyonOptimizationMethodsforCyber-physicalNetworksBabakAslania,ShimaMohebbia,

展开>> 收起<<

The State-of-the-Art Survey on Optimization Methods for Cyber-physical Networks.pdf

共33页,预览5页

还剩页未读，继续阅读

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

The State-of-the-Art Survey on Optimization Methods for Cyber-physical Networks

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: