A branch and bound algorithm for the robust spanning tree problem with interval data

DOI10.1016/j.ejor.2003.10.008zbMath1071.90047OpenAlexW1971456873MaRDI QIDQ706974

Luca Maria Gambardella, Roberto Montemanni

Publication date: 9 February 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2003.10.008

zbMATH Keywords

Branch and boundInterval dataRobust optimizationSpanning tree problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion ⋮ On exact solutions for the minmax regret spanning tree problem ⋮ A multi-population hybrid biased random key genetic algorithm for hop-constrained trees in nonlinear cost flow networks ⋮ A branch and bound algorithm for the minimax regret spanning arborescence ⋮ Restricted robust uniform matroid maximization under interval uncertainty ⋮ Minimax regret spanning arborescences under uncertain costs ⋮ The Minmax Regret Reverse 1-Median Problem on Trees with Uncertain Vertex Weights ⋮ Optimality conditions for interval valued optimization problems ⋮ A fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertainty ⋮ Minmax regret bottleneck problems with solution-induced interval uncertainty structure ⋮ On a constant factor approximation for minmax regret problems using a symmetry point scenario ⋮ 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 ⋮ Simulated annealing algorithm for the robust spanning tree problem ⋮ Combinatorial two-stage minmax regret problems under interval uncertainty ⋮ Heuristics for the central tree problem ⋮ A Benders decomposition approach for the robust spanning tree problem with interval data ⋮ 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 ⋮ A polynomial solvable minimum risk spanning tree problem with interval data ⋮ Combinatorial optimization in system configuration design ⋮ The minimum spanning tree problem with fuzzy costs ⋮ Interval data minmax regret network optimization problems ⋮ An approximation algorithm for interval data minmax regret combinatorial optimization problems ⋮ Robust discrete spanning tree problem: local search algorithms

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Robust discrete optimization and its applications
• A branch and bound algorithm for the robust shortest path problem with interval data.
• On the complexity of the robust spanning tree problem with interval data
• Two Algorithms for Generating Weighted Spanning Trees in Order
• The robust spanning tree problem with interval data
• Unnamed Item

This page was built for publication: A branch and bound algorithm for the robust spanning tree problem with interval data