## 4 Search Space Reduction for Tackling Computational Challenges on Large-Scale Networks  
The dynamic programming algorithm and the feasible solution construction method in the proposed Lagrangian relaxation framework are time-consuming when dealing with large-scale problems. Some search space reduction methods can deploy to reduce computational challenges in large-scale networks. Considering that the single-task route transmission process is mainly limited by time-dependent constraints, we divide the boundaries of possible transmission nodes of a task according to its start time and termination time. In other words, the set of possible transmission nodes for each task is considered a non-complete binary tree. Meanwhile, we record the non-complete binary trees of all tasks, calculate the overlap between all binary trees, and save the nodes and links that may violate the capacity constraint into the set. Finally, only the nodes and links in this set are considered when checking the capacity constraint.  
On the other hand, we find that the search space of the M4 model can be further reduced. Specifically, we first explain the dual-route concept. The dual-route is defined as: for any task \(d\), if the cost of the optimal route under its current route set \(D_{d}\) is \(N^{*}_{d0}\), and there exists a suboptimal route with route cost \(N^{*}_{d0,laid}\) and \(N^{*}_{d0,laid}-N^{*}_{d0}\leq\varepsilon\) (\(\varepsilon\) is the cost difference threshold), while the global impact degree of this suboptimal route is smaller than the global impact degree of the optimal route, the suboptimal route corresponding to route cost \(N^{*}_{d0,laid}\) is called the dual-route of the current optimal route. Due to the large number of tasks, the size of the inter-satellite network, and the existence of task aggregation, the possibility of a dual route for each task is very high. Therefore, we check and record the dual-routes for each task before proceeding with the feasible solution construction process. If a dual-route exists for a task, the optimal route for the task is replaced, while the decision variable \(y_{d(l=dual)}\) in the M4 model is determined directly. This process greatly reduces the search space of the solver when computing the M4 model. In addition to the parameter definitions in model M4, we have added some parameters, shown in Table 6.  
Therefore, we add the redundancy constraint (47) to the M4 model. Because the dual-route of task d must exist in the set of suboptimal routes, we directly constrain the decision variable \(y_{d(l=dual)}\) corresponding to the dual-route to reduce the solution time of the model. The specific improved model (denoted as M5) is shown below.  
\[Min\sum_{d\in D}\sum_{I\in[0,2]^{H_{d}}|+|b_{d}|-1]}y_{dl}N_{dl} \tag{42}\]  
\[\sum_{d\in\Gamma(i,\omega,\omega,\omega^{\prime})}x_{d,(i,s,w)}=Cap_{(i,s,w)}, \forall(i,s,w)\in P \tag{43}\]  
\[\sum_{d\in\Upsilon(i,\omega,\omega,\omega^{\prime})}x_{d,(i,j,s,\varepsilon,w,\omega^{\prime})}=Cap_{(i,j,s,\varepsilon,w,\omega^{\prime})},\forall(i,j,s, e,w,w^{\prime})\in B \tag{44}\]  
\[\sum_{k\in[0,|p_{d}|+|b_{d}|-1]}2^{k}x_{dk}=\sum_{l\in[0,2]^{H_{d}}|+|b_{d}|-1]} y_{dl},\ \ \ d\in D \tag{45}\]  
\[\sum_{l\in[0,2]^{H_{d}}|+|b_{d}|-1]}y_{dl}=1,\ \ d\in D \tag{46}\]  
\[y_{d(l=dual)}=1,d\in Data_{dual} \tag{47}\]  
\[x_{dk},y_{dl}\in\{0,1\},d\in D,k\in[0,|p_{d}|+|b_{d}|-1],\ l\in\left[0,2]^{|p _{d}|+|b_{d}|}-1\right] \tag{48}\]