Optimization Online


Robust constrained shortest path problems under budgeted uncertainty

Artur Alves Pessoa(artur***at***producao.uff.br)
Luigi di Puglia Pugliese(luigi.dipugliapugliese***at***unical.it)
Francesca Guerriero(francesca.guerriero***at***unical.it)
Michael Poss(mjposs***at***gmail.com)

Abstract: We study the robust constrained shortest path problem under resource uncertainty. After proving that the problem is \NPhard in the strong sense for arbitrary uncertainty sets, we focus on budgeted uncertainty sets introduced by Bertsimas and Sim (2003) and their extension to variable uncertainty by Poss (2013). We apply classical techniques to show that the problem with capacity constraint can be solved in pseudo-polynomial time. However, we prove that the problem with time windows is \NPhard in the strong sense when $\Gamma$ is not fixed, using a reduction from the independent set problem. We introduce then new robust labels that yield dynamic programming algorithms for the problems with time windows and capacity constraints. The running times of these algorithms are pseudo-polynomial when $\Gamma$ is fixed, exponential otherwise. We present numerical results for the problem with time windows which show the effectiveness of the label-setting algorithm based on the new robust labels. Our numerical results also highlight the reduction in price of robustness obtained when using variable budgeted uncertainty instead of classical budgeted uncertainty.

Keywords: Constrained shortest path, Robust optimization, Budgeted uncertainty, Dynamic programming, NP-hard

Category 1: Combinatorial Optimization

Category 2: Robust Optimization

Citation: September 2014

Download: [PDF]

Entry Submitted: 10/15/2014
Entry Accepted: 10/15/2014
Entry Last Modified: 10/15/2014

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