# Case Study: Stochastic Multicommodity Network Flow Problem

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.

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

Dataset 17,654 63 27,668 18.53 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) 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
——————————————————————–

Dataset 17,717 63 27,652 163.77 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) 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
——————————————————————–

Dataset 14 + 280 63 26,636 25.88 # of Variables # of Scenarios Objective Value Solving Time, PC 3.14GHz (sec) 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.