This paper studies the multi-tier tree (MTT) problem, a generalization of the Steiner-tree problem, in which the paper is 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 trades 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 the paper must choose between competing communication technologies) and in the transportation setting (where the cost incurred determines the type of access provided between two points). This paper develops two solution approaches for the problem. It first develops a recursive heuristic for the MTT problem, and obtains 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, the paper develops a dual-based solution procedure for this problem, and conduct an extensive computational study to test the efficiacy of the procedure. The present 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 reasonable amount of time.
