Optimization Online


Minimum Cost Flow Problems with Value-at-Risk and Conditional Value-at-Risk Flow Losses under Topological Uncertainty

Qipeng P. Zheng (qipeng.zheng***at***mail.wvu.edu)
Siqian Shen (siqian***at***umich.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 disaster-relief or other uncertain-environment related applications. Given any feasible arc flow solution to a minimum cost flow (MCF) problem, there exist one or multiple path-and-cycle flow representations, conveying positive flow between every pair of origin and destination nodes via directed paths and cycles. Being consistent with real-world 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 Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR) constraints, respectively. Moreover, we develop a linear program to compute all possible minimum flow losses in an arc failure scenario. For SMCF-VaR, 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 SMCF-VaR and SMCF-CVaR, 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, Value-at-Risk, Conditional Value-at-Risk, mixed-integer programming

Category 1: Network Optimization

Category 2: Stochastic Programming

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 05/31/2012
Entry Accepted: 05/31/2012
Entry Last Modified: 06/01/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society