Single Commodity Stochastic Network Design Under Probabilistic Constraint with Discrete Random Variables
作者研究单种商品流网络设计问题，其中节点需求是随机的。目标是在满足可靠性约束（所有需求以指定概率被满足）和确定性约束的前提下，最小化节点和弧上的容量建设成本。作者将可靠性约束用Gale-Hoffman可行性不等式表示，并通过消除技术减少不等式数量。巧妙利用p-有效点概念，将问题转化为线性规划（LP）并松弛，p-有效点与LP解同时生成。利用需求的联合分布获得未被消除的随机不等式的p-有效点，并通过求解多选背包问题生成这些点。模型可应用于电力系统、防洪网络、疏散设施、停车场、金融网络、云计算等规划。文中给出了数值算例。
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.