## 4 Solution Approach
### Getting Primal Feasible Solutions  
By applying the Lagrangean Relaxation Method and the Subgradient Method to solve these problems, we can not only determine a theoretical lower bound from the primal feasible solution, but we have also found some helpful hints for the primal feasible solution that are iterated when solving the dual problem.  
Heuristics for Getting Primal Feasible Solutions  
Two stages are introduced in our heuristics for getting the primal feasible solution: the first stage is the multicast routing problem; the second is the capacity assignment and delay calculation.  
Stage 1: Multicast Routing  
There are some hints to be found within the Lagrangean Relaxation Method's Lagrangean Multipliers. In our multicast routing assignment, the set of routing decision variable \(\{x_{p}\}\)'s corresponding multipliers can be used as each link's arc weight. This way, highly loaded links can be avoided by considering the capacity allocation output from the last iteration's dual problem. Methods such as Dijkstra Algorithm or [PERSON]'s minimum spanning tree algorithm, normally used for finding the shortest path, are utilized to find multicast trees for each multicast group. The shortest path algorithm and the complexity of our heuristic can be chosen in stage 1 is \(O({N}/{N}^{2})\). In this stage, the routing algorithm can be summarized as follows:  
Step 1: For each group \(s\), each link \(l\)'s arc weight \(=\sum\limits_{d\in D_{s}}\mu_{sdl}^{1}\), which is obtained from LR problem and presents the degree of importance of each shortest path.  
Step 2: Run the Dijkstra algorithm to determine the OD path \(p\) of each multicast group \(s\).  
Stage 2: Capacity Assignment and Delay Calculation  
According to the previous stage, the routing path for each source to reach their destinations can be decided. In this stage, the number of paths passing through the link needs to be calculated in each link's traffic path. Meanwhile, they cannot be violated by Constraint (8).  
Having determined every links' traffic flow, we propose a heuristic which steps are described in Algorithm 1 to find a minimal inter-delay. Through this, each link's allocation capacity can be determined. The time complexity of each iteration is \(O({{l}}/{N}^{2})\), and below is the pseudo code of our heuristic. A flow chart illustrates the primal feasible solution in Figure 10.  
```
//Input:all links'trafficflowobtainedfromstage1 //Output:eachlink'scapacityallocation //findanticipatedintra-delayforeachsource-destinationpath foreachlinkl(\(i,j\)) { maximalavailablelinkcapacityforeachlink= nodecapacity*linktraffic/sumofthetotaltrafficfromthenode; } computeeachODpath'sintra-delaywithmaximalavailablecapacity; foreachgroup\(s\) { max_intra_delay=themaximalintra-delayamongODpaths; } \max_inter_delay=themaximal{max_intra_delay*group'sweight;} anticipatedintra-delay=max_inter_delay/thebelonginggroup'sweightofthepath; //assignlinkcapacityperpath foreachpath'sbottomlink\(l(i,j)\)tosource { adjustcapacity(\(l(i,j)\),0); if(eachpath'santicipatedintra-delay!=delayof\(l(i,j)+otherlink'sdelay) { parent=delayof\(l(i,j)\);  adjustcapacity(\(pre\_l\)(\(i,j)\),parent); } }
```  
**Algorithm 1**Capacity assignment and delay calculation.  
```
//computeinter-delayT=anygroup'sintra-delay*thegroup'sweight; returninter-delayT;
```