## 3 Lagrangian Relaxation-Based Solution Approach
### Solution Framework  
As shown in Figure 4, we extend the Lagrangian relaxation framework (Algorithm 1.) to solve the multi-task ISRPTWC. Herein, the inter-satellite topology information and the set of tasks are the inputs, the time-space state network is constructed, and the algorithm parameters are initialized based on the input information. Then, after using the reduced solution space approach, a set of subproblems of the multi-task ISRPTWC are solved by the proposed dynamic programming algorithm to obtain the lower bound cost. After calculating the solutions to the subproblems, the nodes and links that violate constraints are eliminated using the feasible solution construction method, and the upper bound cost is calculated. Finally, the Lagrange multiplier is updated by the subgradient formula and determines whether the termination condition is reached. The specific steps are as follows.  
Figure 4: Lagrangian relaxation solving framework.  
```
// Initialization parameters. Set the iterations \(k_{i}\): Initialize \(LB_{b}\), \(UB_{0}\) and \(\lambda_{1}(n)\), \(\lambda_{2}(e)\) to zero; Initialize \(LB^{*}=-\infty\), \(UB^{*}=+\infty\), \(\theta^{0}\in[0,2]\); Define termination conditions:(1) Reaching the maximum iterations. (2) Gap of the lower bound and the upper bound \(\leq 1\%\); // Constructing a time-space state network based on the input information.  While termination condition is false: For each iteration k do: // Generate and update \(LB_{k}\) Use the dynamic programming algorithms to find the lowest cost route for each task; // The algorithm is in Section 3.3 Update \(LB^{*}\) by \(\max(LB_{k},LB^{*})\); // Generate and update \(UB_{k}\). Use the feasible solution construction method to find the lowest cost route for all tasks while meeting all constraints; // The method is in Section 3.4 Update \(UB^{*}\) by \(\min(UB_{k},UB^{*})\); // Subgradient calculation. // The calculation process is shown in Section 3.2. Calculate the capacity of each node and link using expression (20); \(\sum\limits_{d\in D}\frac{\sum\limits_{(i,j,s,e,w,w^{\prime})}}{\sum\limits_{d \in D}y(d,i,j,s,e,w,w^{\prime})}\) (20) Calculate the subgradient by equation (21) and record all non-zero subgradients to the set \(S_{t}\); \[\left\{\begin{aligned} \
abla\lambda_{1}(n)&=\max \left\{\sum\limits_{d\in D}\sum\limits_{(i,j,s,e,w,w^{\prime})\in\phi_{(i,e,w ^{\prime})}}y(d,i,j,s,e,w,w^{\prime})-Cap_{(j,e,w^{\prime})},0\right\}\\ &\
abla\lambda_{2}(e)&=\max\left\{\sum\limits_{d \in D}y(d,i,j,s,e,w,w^{\prime})-Cap_{(i,j,s,e,w^{\prime})},0\right\}\end{aligned}\right.\] (21) Update all node and link multipliers through equation (22); \[\left\{\begin{aligned} \lambda_{1}(n)&=\max \left\{\lambda_{1}(n)+\theta^{k}\
abla\lambda_{1}(n),0\right\}\\ \lambda_{2}(e)&=\max\left\{\lambda_{2}(e)+\theta^{k} \
abla\lambda_{2}(e),0\right\}\end{aligned}\right.\] (22) // Since all nodes are not merged into the cost during the calculation, we transfer the cost of all nodes to the cost of the corresponding links, updating the cost using equation (23). \[\xi(d,i,j,s,e,w,w^{\prime})=\frac{1}{Pr_{id}}c\left(d,i,j,s,e,w,w^{\prime} \right)+\lambda_{1}(n)+\lambda_{2}(e)\] (23) Update the gradient step using equation (24); \[\theta^{k+1}=\frac{UB_{k}-LB_{k}}{\left|S_{t}\right|_{2}}\theta^{k}\] (24) // Calculate the gap value and update the iteration k. The gap between \(LB^{*}\) and \(UB^{*}\) is obtained by \(\frac{UB^{*}-LB^{*}}{UB^{*}}\times 100,\ k=k+1\); end
```  
**Algorithm 1** Lagrangian relaxation-based solution framework.