A branch and bound algorithm for the robust shortest path problem with interval data.

DOI10.1016/j.orl.2003.08.002zbMath1045.90086OpenAlexW2103776399MaRDI QIDQ1426725

Roberto Montemanni, Alberto V. Donati, Luca Maria Gambardella

Publication date: 15 March 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2003.08.002

zbMATH Keywords

Branch and boundInterval dataRobust optimizationShortest path problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (39)

The minmax regret robust shortest path problem in a finite multi-scenario model ⋮ A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem ⋮ Ranking function-based solutions of fully fuzzified minimal cost flow problem ⋮ A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs ⋮ New models for the robust shortest path problem: complexity, resolution and generalization ⋮ Restricted robust uniform matroid maximization under interval uncertainty ⋮ A double oracle approach to minmax regret optimization problems with interval data ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Deterministic risk control for cost-effective network connections ⋮ The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows ⋮ Algorithms for the minmax regret path problem with interval data ⋮ Minmax regret combinatorial optimization problems with ellipsoidal uncertainty sets ⋮ On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data ⋮ An integer linear programming formulation and heuristics for the minmax relative regret robust shortest path problem ⋮ Shortest path network problems with stochastic arc weights ⋮ Time dependent vehicle routing problem with a multi ant colony system ⋮ The solution and duality of imprecise network problems ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ An enhanced exact procedure for the absolute robust shortest path problem ⋮ Linear programming with interval right hand sides ⋮ A branch and bound algorithm for the robust spanning tree problem with interval data ⋮ Finding the shortest path with honey-bee mating optimization algorithm in project management problems with constrained/unconstrained resources ⋮ Minimizing maximum risk for fair network connection with interval data ⋮ Combinatorial algorithms for the minimum interval cost flow problem ⋮ Reduction approaches for robust shortest path problems ⋮ A Benders decomposition approach for the robust spanning tree problem with interval data ⋮ Probabilistic models for the Steiner Tree problem ⋮ A new model for path planning with interval data ⋮ Routing Optimization Under Uncertainty ⋮ Min-max and min-max regret versions of combinatorial optimization problems: A survey ⋮ Computing and minimizing the relative regret in combinatorial optimization with interval data ⋮ Distributionally robust maximum probability shortest path problem ⋮ The most likely path on series-parallel networks ⋮ Robustness in operational research and decision aiding: a multi-faceted issue ⋮ Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights ⋮ An approximation algorithm for interval data minmax regret combinatorial optimization problems ⋮ The robust shortest path problem in series -- parallel multidigraphs with interval data ⋮ Robust Optimization for the Hazardous Materials Transportation Network Design Problem ⋮ Robust optimization for the hazardous materials transportation network design problem

Cites Work

• A note on two problems in connexion with graphs
• The computational complexity of the relative robust shortest path problem with interval data
• Robust discrete optimization and its applications
• On the robust shortest path problem.
• An exact algorithm for the robust shortest path problem with interval data
• Shortest path problems with partial information: Models and algorithms for detecting dominance
• The robust spanning tree problem with interval data

This page was built for publication: A branch and bound algorithm for the robust shortest path problem with interval data.