Optimization Online


Risk Averse Shortest Path Interdiction

Yongjia Song(ysong3***at***vcu.edu)
Siqian Shen(siqian***at***umich.edu)

Abstract: We consider a Stackelberg game in a network, where a leader minimizes the cost of interdicting arcs and a follower seeks the shortest distance between given origin and destination nodes under uncertain arc traveling cost. In particular, we consider a risk-averse leader, who aims to keep high probability that the follower's traveling distance is longer than a given threshold, interpreted by a chance constraint. For the case with a wait-and-see follower, i.e., the follower selects a shortest path after seeing realizations of the random arc cost, we propose a branch-and-cut algorithm and apply lifting techniques to exploit the combinatorial structure of the risk-averse leader's interdiction problem. For the case with a here-and-now follower, we formulate a monolithic mixed-integer linear programming formulation for benchmark. We demonstrate the computational efficacy of our approaches, risk-averse interdiction solution patterns, and result sensitivity, via testing instances of randomly generated grid networks and real-world transportation networks.

Keywords: Stochastic network interdiction; chance constraint; mixed-integer programming; branch-and-cut; lifting

Category 1: Network Optimization

Category 2: Integer Programming (0-1 Programming )

Category 3: Stochastic Programming


Download: [PDF]

Entry Submitted: 02/18/2016
Entry Accepted: 02/22/2016
Entry Last Modified: 02/18/2016

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