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
(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 variables
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.5GHz (sec)
Dataset 3193 1000 11034 0.02
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
(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
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.5GHz (sec)
Dataset 3193 1000 0.1872 0.99
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
(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
——————————————————————–

# of Variables # of Scenarios Objective Value Solving Time, PC 3.7GHz (sec)
Dataset 3193 1000 14060 913.46
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.

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