This paper studies the multi-tier tree (MTT) problem, a generalization of the Steiner-tree problem, in which we are given a graph with its nodes partitioned into several tiers (grades), and grade dependent edge-costs. The MTT problem seeks the cost minimizing choice of grades for the edges such that every pair of nodes, say at tiers t′ and t″ ≥ t′, is connected by a path containing grade-t′ or better (grade) edges. The MTT problem arises in the telecommunication setting (where we must choose between competing communication techologies) and in the transportation setting (where the cost incurred determines the type of access provided between two points). In this paper, we develop two solution approaches for the problem. We first develop a recursive heuristic for the MTT problem, and obtain data-independent bounds for MTT problems with 3-tiers. For one case, the bound on the performance ratio of the recursive heuristic is 1.52241. Next, we develop a dual-based solution procedure for this problem, and conduct an extensive computational study to test the efficacy of the procedure. Our study, with problems having up to 2000 nodes, 6000 edges and 5 tiers (with up to 60,000 integer and 24 million continuous variables), shows that the method is quite effective in generating solutions within 6% of optimality in a resonable amount of time.
