## 4 Problem Statement and Algorithm Framework
### Algorithm Framework  
The problem described in the previous subsection is an ILP and can be solved by the branch-and-bound scheme [46], where the lower and upper bounds of regions/branches are obtained by solving the relaxation problem. According to the cutting plane approach [3], the relaxation can be iteratively tightened by adding valid inequalities to the formulation. Following, we briefly describe the algorithmic steps.  
Relaxation: Relax the original problem and represent the relaxation problem in the standard form. In this stage, we transform the binary variable \(x_{(u,v)}^{(s,k),(s,l)}\) in the original ILP into a continuous variable \(\widetilde{x}_{(u,v)}^{(s,k),(s,l)}\) and formulate the corresponding problem with ignoring the integer constraint (14). That is, the relaxation problem of the original ILP (RILP), as follows:  
\[(\text{P2}):f(\widetilde{x}_{(u,v)}^{(s,k),(s,l)})=\max_{\widetilde{x}_{(u,v )}^{(s,k),(s,l)}}\sum_{s\in S}\sum_{u,v\in N^{\prime}\in P}\sum_{k,l\in N^{ \prime\prime}}-\alpha_{(u,v)}^{(s,k),(s,l)}\widetilde{x}_{(u,v)}^{(s,k),(s,l) }\lambda^{(s,k),(s,l)}.\]  
Upper bound: Using the simplex algorithm to find a solution \(x_{r}\) to the objective function of RILP and store the value \(Z=f(x_{r})\). \(Z\) will denote the best solution found so far, and will be used as an upper bound of the original ILP on the feasible region \(D\). We denote the upper bound as \(\sup{(ILP)}=Z\) and the optimal value of the objective function of the original ILP as \(Z^{*}\), where \(Z^{*}\leq Z\). If \(x_{r}\) is an integer, \(Z^{*}=Z\) is the optimal solution for the original problem.  
Branching: If the solution \(x_{r}\) is not an integer, we remove the region \(I_{r}<x_{r}<I_{r}+1\) (where \(I_{r}\) is the integer part of \(x_{r}\)) that does not contain any integer solution on the feasible region \(D\). Thus, \(D\) is divided into two disjoint parts \(D_{1}\) and \(D_{2}\). According to the invariant objective function of RILP, we use \(D_{1}\) and \(D_{2}\) as feasible regions respectively. That is, adding two constraints \(x_{r}\leq I_{r}\) and \(x_{r}\geq I_{r}+1\) respectively in the original problem, so as to construct two sub-problems \(Sub_{1}\) and \(Sub_{2}\). If the optimal solution of these two problems is still not an integer, then we continue to choose a non-integer solution \(x_{r,sub_{1}}\) and decompose the corresponding sub-problem \(Sub_{1}\) into two sub-problems. For each sub-problem, if the solution is not a integer, as well as the optimal value of the objective function \(Z_{sub}\geq\sup{(ILP)}\), we \"prune\" the corresponding feasible region.  
Lower bound: If the solution of sub-problem \(Sub_{1}\) is an integer and the optimal value of the objective function is \(Z_{sub_{1}}\), we can obtain a lower bound of the original ILP \(Z^{*}\), denoted as \(\inf{(ILP)}=Z_{sub_{1}}\).  
Optimal solution: Repeat the aforementioned branching and delimiting process to update the upper and lower bounds of original ILP. Tighten iteratively and \"prune\" the \"branch\" until all sub-problems cannot be branched, then we find the optimal solution \(Z^{*}=\sup{(ILP)}\).