Loss-constrained minimum cost flow under arc failure uncertainty with applications in risk-aware kidney exchange

Qipeng P. Zheng, Siqian Shen and Yuhui Shi

IISE Transactions, 2015, vol. 47, issue 9, 961-977

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.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2014.991476 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:47:y:2015:i:9:p:961-977

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2014.991476

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().