Case study background and problem formulations
Optimization package Gurobi should be installed to run this case study.
(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 |
____________________________________________________________________________________________________________________________________
Dataset2 | Problem Statement | Data | Solution | 3193 | 1000 | 11033.8 | 0.06 |
____________________________________________________________________________________________________________________________________
PROBLEM 2: 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 | 21.4 |
Dataset1.2 | 3193 | 1000 | 5324.9 | 22.9 | |||
Dataset1.3 | 3193 | 1000 | 5714.4 | 29.7 | |||
Dataset1.4 | 3193 | 1000 | 5859.7 | 31.9 |
____________________________________________________________________________________________________________________________________
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 |
PROBLEM 3: 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.4 |
Dataset1.2 | 3193 | 1000 | 0.05 | 3600.1 | |||
Dataset1.3 | 3193 | 1000 | 0.01 | 3600.3 | |||
Dataset1.4 | 3193 | 1000 | 0.005 | 3600.0 |
____________________________________________________________________________________________________________________________________
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 4: 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 | 89.7 |
Dataset1.2 | 3193 | 1000 | 0.05 | 85.4 | |||
Dataset1.3 | 3193 | 1000 | 0.01 | 101.4 | |||
Dataset1.4 | 3193 | 1000 | 0.005 | 94.7 |
____________________________________________________________________________________________________________________________________
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 |
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);
• Conditional Value-at-Risk (CVaR) of the path cost with a specified confidence level;
• Probability of Exceedance (POE) of path cost with a specified threshold;
• Buffered Probability of Exceedance (bPOE) of path cost with a specified threshold.