The QoS requirement of a connection is given as a set of constraints, which can be link constraints, path constraints, or tree constraints. A feasible path (tree) is one that has sufficient residual resources to satisfy the QoS constraints of a connection. In this solution some complicated constraint are relaxed and the primal problem is decomposed into several sub problems. Primal feasible solutions are obtained by some heuristics and a link set adjusting method is proposed by the aggregate flow on links. In computational experiments, the proposed algorithm determines solutions that are within a few percent of an optimal solution with 30 nodes in the QoS model. In terms of performance, our solution has more significant improvement than simple heuristics. The improvement on the total revenue can reach 12% on the average in the QoS model. The improvement of heuristics 2 in the QoS model on the total revenue can reach 8% on the average.