Case Study: Shortest Path in a Stochastic Weighted Graph using Average, CVaR, POE and bPOE Performance Functions

Case study background and problem formulations

Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox, PSG MATLAB Subroutines and PSG R. Optimization package Gurobi should be installed to run this case study.

PROBLEM 1: problem_shortest_path_average (formulation with Boolean variables) Minimize Avg (minimizing expected cost (length) of a path)nsubject to
Linearmulti = 0 (path representation constraints) Box constraints (defines Boolean variables)Calculate:ncvar_risk_gnbPOE_gnvar_risk_gnpr_pen_g ——————————————————————– Avg = Average
Linearmulti = System of linear constraintsncvar_risk_g = CVaR for GainnbPOE_g = Buffered Probability of Exceedance for Gainnvar_risk_g = VaR for Gainnpr_pen_g = Probability of Exceedance for Gai
Box constraints = constraints on individual decision variables ——————————————————————–

Dataset1	3193	1000	3149.32	0.03
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

Download other datasets in Run-File Environment. Instructions for importing problems from Run-File to PSG MATLAB.

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.50GHz (sec)
Dataset2	Problem Statement	Data	Solution	3193	1000	11033.8	0.06

PROBLEM 2: problem_the_most_shortest_path_pr_pen (formulation with Boolean variables) Minimize pr_pen (Probability of Exceedance (POE) of path cost (length) of a specified threshold)nsubject to
Linearmulti = 0 (path representation constraints) Box constraints (defines Boolean variables)nnpr_pen = Probability of Exceedance
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variables
Data and solution in Run-File Environmentn

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Dataset1.1	Cycle statement	Data	Solution	3193	1000	0.1	3600.6
Dataset1.2				3193	1000	0.05	3600.55
Dataset1.3				3193	1000	0.01	1892.95
Dataset1.4					1000	0.005	300.74

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Dataset2	Problem Statement	Data	Solution	3193	1000	0.0449	3611.12

Data and solution in MATLAB Toolboxn

Problem Datasets		# of Variables	# of Scenarios
Dataset1	Data	3193	1000
Dataset2	Data	3193	1000

Data and solution in MATLAB Subroutinesn

Problem Datasets			# of Variables	# of Scenarios
Dataset1	MATLAB code	Data	3193	1000
Dataset2	MATLAB code	Data	3193	1000

Data and solution in R Environmentn

Problem Datasets			# of Variables	# of Scenarios
Dataset1	R code	Data	3193	1000
Dataset2	R code	Data	3193	1000

PROBLEM 3: problem_the_most_shortest_path_bPOE (formulation with Boolean variables) Minimize bpoe (Buffered Probability of Exceedance) of path cost (length) with a specified threshold)nsubject to
Linearmulti = 0 (path representation constraints) Box constraints (defines Boolean variables)nnbpoe= Probability of Exceedance
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variables
Data and solution in Run-File Environmentn

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Dataset1.1	Cycle statement	Data	Solution	3193	1000	0.1	23.38
Dataset1.2				3193	1000	0.05	25.41
Dataset1.3				3193	1000	0.01	36.60
Dataset1.4				3193	1000	0.005	38.80

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Dataset2	Problem Statement	Data	Solution	3193	1000	0.01932	6269.94

Data and solution in MATLAB Toolboxn

Problem Datasets		# of Variables	# of Scenarios
Dataset1	Data	3193	1000
Dataset2	Data	3193	1000

Data and solution in MATLAB Subroutinesn

Problem Datasets			# of Variables	# of Scenarios
Dataset1	MATLAB code	Data	3193	1000
Dataset2	MATLAB code	Data	3193	1000

Data and solution in R Environmentn

Problem Datasets			# of Variables	# of Scenarios
Dataset1	R code	Data	3193	1000
Dataset2	R code	Data	3193	1000

PROBLEM 5: problem_alpha_shortest_path_cvar (formulation with Boolean variables) Minimize Cvar_risk (Conditional Value-at-Risk (CVaR) of the path cost with a specified confidence level)nsubject to
Linearmulti = 0 (path representation constraints) Box constraints (defines Boolean variables) ——————————————————————– Cvar_risk = Conditional Value-at-Risk
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variables ——————————————————————– Data and solution in Run-File Environmentn

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.14GHz (sec)
Dataset1.1	Cycle statement	Data	Solution	3193	1000	4928.9	14.30
Dataset1.2				3193	1000	5324.9	15.78
Dataset1.3				3193	1000	5714.4	11.86
Dataset1.4				3193	1000	5859.7	16.61

Problem Datasets				# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.50GHz (sec)
Dataset2	Problem Statement	Data	Solution	3193	1000	14059.8	2531.73

Data and solution in MATLAB Toolboxn

Problem Datasets		# of Variables	# of Scenarios
Dataset1	Data	3193	1000
Dataset2	Data	3193	1000

Data and solution in MATLAB Subroutinesn

Problem Datasets			# of Variables	# of Scenarios
Dataset1	MATLAB code	Data	3193	1000
Dataset2	MATLAB code	Data	3193	1000

Data and solution in R Environmentn

Problem Datasets			# of Variables	# of Scenarios
Dataset1	R code	Data	3193	1000
Dataset2	R code	Data	3193	1000

CASE STUDY SUMMARYn A graph consists of a set of vertices (nodes) and arcs (edges) connecting vertices. In deterministic setting each arc is characterized by a single cost. Depending on the application, the cost may be travel time, financial cost, etc. The cost of a path is the sum of the costs of arcs in the path. The deterministic shortest path problem finds a path from a starting point to a final point with minimal cost.This case study solves problems with stochastic costs of arcs (i.e., cost of each arc is a random value). We formulated problems for finding a path with the minimal:nn• Expected cost (length);n• Probability of Exceedance (POE) of path cost with a specified threshold;n• Buffered Probability of Exceedance (bPOE) of path cost with a specified threshold.n• Value-at-Risk (VaR) of the path cost with a specified confidence level;n• Conditional Value-at-Risk (CVaR) of the path cost with a specified confidence level;