  Robust optimization is one of the fundamental approaches to deal with
uncertainty in combinatorial optimization. This paper considers the robust
spanning tree problem with interval data, which arises in a variety of
telecommunication applications. It proposes a constraint satisfaction approach
using a combinatorial lower bound, a pruning component that removes infeasible
and suboptimal edges, as well as a search strategy exploring the most uncertain
edges first. The resulting algorithm is shown to produce very dramatic
improvements over the mathematical programming approach of Yaman et al. and to
enlarge considerably the class of problems amenable to effective solutions
