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

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
(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)Calculate:
cvar_risk_g
bPOE_g
var_risk_g
pr_pen_g
——————————————————————–
Avg = Average
Linearmulti = System of linear constraints
cvar_risk_g = CVaR for Gain
bPOE_g = Buffered Probability of Exceedance for Gain
var_risk_g = VaR for Gain
pr_pen_g = Probability of Exceedance for Gain
Box constraints = constraints on individual decision variables
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec)
Dataset1 3193 1000 3149.32 0.03
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)
subject to
Linearmulti = 0 (path representation constraints)
Box constraints (defines Boolean variables)

pr_pen = Probability of Exceedance
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variables

Data and solution in Run-File Environment

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 Toolbox

Problem Datasets # of Variables # of Scenarios
Dataset1 Data 3193 1000
Dataset2 Data 3193 1000
Data and solution in MATLAB Subroutines

Problem Datasets # of Variables # of Scenarios
Dataset1 MATLAB code Data 3193 1000
Dataset2 MATLAB code Data 3193 1000
Data and solution in R Environment

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)
subject to
Linearmulti = 0 (path representation constraints)
Box constraints (defines Boolean variables)

bpoe= Probability of Exceedance
Linearmulti = System of linear constraints
Box constraints = constraints on individual decision variables

Data and solution in Run-File Environment

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 Toolbox

Problem Datasets # of Variables # of Scenarios
Dataset1 Data 3193 1000
Dataset2 Data 3193 1000
Data and solution in MATLAB Subroutines

Problem Datasets # of Variables # of Scenarios
Dataset1 MATLAB code Data 3193 1000
Dataset2 MATLAB code Data 3193 1000
Data and solution in R Environment

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)
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
——————————————————————–
Data and solution in Run-File Environment

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 Toolbox

Problem Datasets # of Variables # of Scenarios
Dataset1 Data 3193 1000
Dataset2 Data 3193 1000
Data and solution in MATLAB Subroutines

Problem Datasets # of Variables # of Scenarios
Dataset1 MATLAB code Data 3193 1000
Dataset2 MATLAB code Data 3193 1000
Data and solution in R Environment

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

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.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:

• Expected cost (length);
• Probability of Exceedance (POE) of path cost with a specified threshold;
• Buffered Probability of Exceedance (bPOE) of path cost with a specified threshold.
• Value-at-Risk (VaR) of the path cost with a specified confidence level;
• Conditional Value-at-Risk (CVaR) of the path cost with a specified confidence level;