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