Single commodity stochastic network design under probabilistic constraint with discrete random variables

Abstract

Single commodity networks are considered, where demands at the nodes are random. The problem is to find minimum cost optimal built in capacities at the nodes and arcs subject to the constraint that all demands should be met on a prescribed probability level (reliability constraint) and some deterministic constraints should be satisfied. The reliability constraint is formulated in terms of the Gale-Hoffman feasibility inequalities, but their number is reduced by elimination technique. The concept of a p-efficient point is used in a smart way to convert and then relax the problem into an LP. The p-efficient points are simultaneously generated with the solution of the LP. The joint distribution of the demands is used to obtain the p-efficient points for all stochastic inequalities that were not eliminated and the solution of a multiple choice knapsack problem is used to generate p-efficient points. The model can be applied to planning in interconnected power systems, flood control networks, design of shelter and road capacities in evacuation, parking lot capacities, financial networks, cloud computing system design, etc. Numerical examples are presented.