Loss-Constrained Minimum Cost Flow Under Arc Failure Uncertainty With Applications In Risk-Aware Kidney Exchange

Keywords

Benders decomposition; conditional value-at-risk; risk-aware kidney exchange; Stochastic minimum cost flow; value-at-risk

Abstract

In this article, we study a Stochastic Minimum Cost Flow (SMCF) problem under arc failure uncertainty, where an arc flow solution may correspond to multiple path flow representations. We assume that the failure of an arc will cause flow losses on all paths using that arc, and for any path carrying positive flows, the failure of any arc on the path will lose all flows carried by the path. We formulate two SMCF variants to minimize the cost of arc flows, while respectively restricting the Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR) of random path flow losses due to uncertain arc failure (reflected as network topological changes). We formulate a linear program to compute possible losses, yielding a mixed-integer programming formulation of SMCF-VaR and a linear programming formulation of SMCF-CVaR. We present a kidney exchange problem under uncertain match failure as an application and use the two SMCF models to maximize the utility/social welfare of pairing kidneys subject to constrained risk of utility losses. Our results show the efficacy of our approaches, the conservatism of using CVaR, and optimal flow patterns given by VaR and CVaR models on diverse instances.

Publication Date

9-2-2015

Publication Title

IIE Transactions (Institute of Industrial Engineers)

Volume

47

Issue

9

Number of Pages

961-977

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/0740817X.2014.991476

Socpus ID

84931578224 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84931578224

This document is currently not available here.

Share

COinS