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

Back to main page
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 n(formulation with Boolean variables)
Minimize Avg (minimizing expected cost (length) of a path)
subject to
Linearmulti = 0 (path representation constraints)
Box constraints (defines Boolean variables)
——————————————————————– Avg = Average
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variablesn——————————————————————–

Dataset	3193	1000	11034	0.02
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.5GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

PROBLEM 2: problem_the_most_shortest_path_bPOE n(formulation with Boolean variables)
Minimize bpoe (Buffered Probability of Exceedance) of path cost (length) with a specified threshold)
subject to
Linearmulti = 0 (path representation constraints)
Box constraints (defines Boolean variables)
——————————————————————–nbpoe= Probability of Exceedance
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variables
——————————————————————–

Dataset	3193	1000	0.1872	0.99
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.5GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

PROBLEM 3: problem_alpha_shortest_path_cvar n(formulation with Boolean variables)
Minimize Cvar_risk (Conditional Value-at-Risk (CVaR) of the path cost with a specified confidence level)
subject 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
——————————————————————–

Dataset	3193	1000	14060	913.46
	# of Variables	# of Scenarios	Objective Value	Solving Time, PC 3.7GHz (sec)
Environments
Run-File	Problem Statement		Data	Solution
Matlab Toolbox			Data
Matlab Subroutines	Matlab Code		Data
R	R Code		Data

CASE STUDY SUMMARY
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. n
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:n• Expected cost (length);n• Buffered Probability of Exceedance (bPOE) of path cost with a specified threshold;n• Conditional Value-at-Risk (CVaR) of the path cost with a specified confidence level.