# Case Study: Stochastic Multicommodity Network Flow Problem

** Case study background and problem formulations**

Instructions for optimization with PSG Run-File, PSG MATLAB Toolbox, PSG MATLAB Subroutines and PSG R.

**PROBLEM: problem_p_multicomm**

Minimize Linear (minimizing network cost)

subject to

Linearmulti = Const1 (network flow constraints for every commodity and scenario)

Prmulti_pen ≤ Const2 (constraint on probability that flow in at least one ark exceeds capacity)

Box constraints (bounds on decision variables)

——————————————————————–

Linearmulti = Linear Multiple

Prmulti_pen = Probability Exceeding Penalty for Loss Multiple

Box constraints = constraints on individual decision variables

——————————————————————–

# of Variables |
# of Scenarios |
Objective Value |
Solving Time, PC 3.14GHz (sec) |
||||

Dataset | 17,654 | 63 | 27,668 | 18.53 | |||
---|---|---|---|---|---|---|---|

Environments |
|||||||

Run-File | Problem Statement | Data | Solution | ||||

Matlab Toolbox | Data | ||||||

Matlab Subroutines | Matlab Code | Data | |||||

R | R Code | Data |

**NOTE:** Problem statement can be simplified using MultiConstraint.

**PROBLEM: problem_c_multicomm**

Minimize Linear (minimizing network cost)

subject to

Cardn_neg ≤ Const3 (constraint on the number of scenarios on which flow in some ark may exceed capacity)

Linearmulti ≤ Const4 (constraint on probability that flow in at least one ark exceeds capacity)

Linearmulti = 0 (network flow constraints for every commodity and scenario with varying demands)

Box constraints (bounds on decision variables)

——————————————————————–

Cardn_neg = Cardinality Negative

Linearmulti = Linear Multiple

Box constraints = constraints on individual decision variables

——————————————————————–

# of Variables |
# of Scenarios |
Objective Value |
Solving Time, PC 3.14GHz (sec) |
||||

Dataset | 17,717 | 63 | 27,652 | 163.77 | |||
---|---|---|---|---|---|---|---|

Environments |
|||||||

Run-File | Problem Statement | Data | Solution | ||||

Matlab Toolbox | Data | ||||||

Matlab Subroutines | Matlab Code | Data | |||||

R | R Code | Data |

**NOTE:** Problem statement can be simplified using MultiConstraint.

**PROBLEM: problem_2st_multicomm**

Minimize Linear (minimizing network cost)

subject to

Pr_pen(Q) ≤ Const2 (constraint on probability that random recourse function exceeds 0)

Box constraints (bounds on decision variables)

——————————————————————–

Pr_pen(Q) = Probability Exceeding Penalty for Recourse

Box constraints = constraints on individual decision variables

——————————————————————–

# of Variables |
# of Scenarios |
Objective Value |
Solving Time, PC 3.14GHz (sec) |
||||

Dataset | 14 + 280 | 63 | 26,636 | 25.88 | |||
---|---|---|---|---|---|---|---|

Environments |
|||||||

Run-File | Problem Statement | Data | Solution | ||||

Matlab Toolbox | Data | ||||||

Matlab Subroutines | Matlab Code | Data | |||||

R | R Code | Data |

**CASE STUDY SUMMARY**

This case study optimizes a stochastic multi-commodity network flow problem. The stochastic multi-commodity network flow problem is formulated as a stochastic programming problem with a probabilistic constraint based on discrete scenarios. For every commodity a pair of source and absorption vertices is defined. Demands in absorption vertices are considered to be random. As a result flows from the source to absorption vertices are random too. The problem finds optimal capacities of arcs in the network by minimizing the total cost of the network subject to constraints. The joint distribution of demands for all commodities is given by a set of scenarios. The flow through an arc is defined as the sum of flows of all commodities through this arc. The total cost of arcs is a linear function of arc capacities. The objective of the optimization is to find capacities of arcs minimizing the total cost of the network and satisfying the random flow constraint with prescribed probability (i.e., a specified probability will be assured that flows in all arcs will not exceed the capacity). A random flow constraint is a chance constraint. We formulate three variants of this constraint: 1) constraint on probability of insufficient capacity at least one arc; 2) constraint on a fraction of scenarios on which network flows may exceed capacities; 3) constraint on probability that random recourse function exceeds 0. Therefore three formulations of the problem are considered.

**References**

• Ruszczynski, A. (2002): Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra.

*Math. Programming*, Ser. A 93, pp. 195–215.

• Prekopa, A. (1995): Stochastic Programming. Kluwer, Dordrecht.