  


Minimum Cost Flow Problems with ValueatRisk and Conditional ValueatRisk Flow Losses under Topological Uncertainty
Qipeng P. Zheng (qipeng.zhengmail.wvu.edu) Abstract: Stochastic minimum cost flow (SMCF) problems have been studied for applications involving random arc capacities or demand uncertainty. This paper considers a SMCF under uncertainty of arc failures, arising in disasterrelief or other uncertainenvironment related applications. Given any feasible arc flow solution to a minimum cost flow (MCF) problem, there exist one or multiple pathandcycle flow representations, conveying positive flow between every pair of origin and destination nodes via directed paths and cycles. Being consistent with realworld applications, we assume that any arc failure will cause flow losses on all paths that use the arc, and for any path having positive flow, one or multiple arc failures will result in the same loss value equaling to the original path flow. We study two problem variants, seeking MCF solutions whose minimum flow losses are bounded by ValueatRisk (VaR) and Conditional ValueatRisk (CVaR) constraints, respectively. Moreover, we develop a linear program to compute all possible minimum flow losses in an arc failure scenario. For SMCFVaR, we reformulate an equivalent deterministic model by defining binary variables indicating violations of the VaR constraint in all scenarios. The paper proposes a decomposition approach for solving both SMCFVaR and SMCFCVaR, which iteratively generates valid cuts to attain optimum. We demonstrate the computational efficacy, and compare the two risk measures by testing on a set of randomly generated instances. Keywords: stochastic minimum cost flow, path flow loss, ValueatRisk, Conditional ValueatRisk, mixedinteger programming Category 1: Network Optimization Category 2: Stochastic Programming Category 3: Integer Programming ((Mixed) Integer Linear Programming ) Citation: Download: [PDF] Entry Submitted: 05/31/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  