## 5 Solution Algorithm
### Branch-and-Cut Algorithm  
The application of the cut plane composed of the above valid inequalities will be illustrated in this section. The cuts and bound improvement suitable for solving the problem in this paper are introduced in this section. The branch-and-cut algorithm is outlined as follows:  
1. Initialize: Set \(T=0\), \(UB=M\), \(LB=0\).
2. Solve the LP relaxation: Obtain \(X^{*}=\left\{x_{1}^{0},x_{2}^{0},x_{3}^{0},...\right\}\). This will detect an optimal solution, an updated upper bound solution or that the problem is infeasible.
3. Branching: According to the most fractional branching strategy to create two new nodes.  
* 4. Fathoming rules: If the node relaxation is infeasible or \(XLS^{\texttt{vs}}_{ij}+XLF_{1 ij}^{\texttt{vs}}+XLF_{2 ij}^{\texttt{vs}}+X_{i}^{ \texttt{vs}}\prec\mathit{cap}^{\texttt{vs}}\) and \(f(x)\prec\mathit{UB}*\tau,\tau\in(0.5,1)\), fathom the node and return to Step 3. Otherwise, continue to Step 5.
* 5. Insert all valid inequalities into the program.
* 6. Solve the LP relaxation of new nodes, respectively.
* 7. Update the upper and lower bounds again.
* 8. If the termination condition is satisfied, end the procedure and input the \(X^{\text{best}}\).  
The pseudocode are presented in Algorithm 1.  
```
1:Step1 Initialize:\(T=0\), \(\mathit{UB}=M\),\(\mathit{LB}=0\).
2:Step2 Solve the LP relaxation, and then obtain \(X^{*}=\{x_{1}^{0},x_{2}^{0},x_{3}^{0},...\}\)
3:while (\(X^{*}=\emptyset\)) do
4: Break
5:if (\(X^{*}\in Z^{+}\)) then
6:STOP, \(X^{\text{best}}=X^{*}\)
7:if (\(X^{*}\
otin Z^{+}\)) then
8:Set \(\mathit{UB}=f(X^{*})\)
9:endif
10:endif
11:endwhile
12:Step3 Branching: According to the most fractional branching strategy.
13:Set: Choose node \(x_{i}^{j}\
ot\in Z^{+}\), set P1: \(x_{i}^{j}\leq\left\lfloor x_{i}^{j}\right\rfloor\); P2: \(x_{i}^{j}\geq\left\lfloor x_{i}^{j}\right\rfloor+1\); T=T+1.
14:Step4 Fathoming: Fathom nodes according to the fathoming rules.
15:Step5 Insert: All valid inequalities (26)-(28) into the program.
16:Step6 Solve: The LP relaxation of P1 and P2, respectively. Obtain \(X_{1}^{*}\) and \(X_{2}^{*}\).
17:Step7 Repeat: Update the upper and lower bounds.
18:while\(X_{1}^{*}=\emptyset\) and \(X_{2}^{*}=\emptyset\)do
19: Break
20:if\(X_{1}^{*}=\emptyset\) and \(X_{2}^{*}\in Z^{+}\)then
21:STOP,\(X^{\text{best}}=X_{2}^{*}\)
22:endif
23:if\(X_{1}^{*}=\emptyset\) and \(X_{1}^{*}\in Z^{+}\)then
24:STOP,\(X^{\text{best}}=X_{1}^{*}\)
25:endif
26:if\(X_{1}^{*}(X_{2}^{*})\in Z^{+},X_{2}^{*}(X_{1}^{*})\
ot\in Z^{+}\)then
27:\(\mathit{LB}=f\left(X_{1}^{*}\right)\) or \(f\left(X_{2}^{*}\right)\), P2(P1): repeat Step 3-Step 5
28:endif
29:if\(X_{1}^{*}\in Z^{+},X_{2}^{*}\in Z^{+}\)then
30:if\(X_{1}^{*}\geq X_{2}^{*}\)then
31:STOP,\(X^{\text{best}}=X_{1}^{*}\)
32:else
33:\(X^{\text{best}}=X_{2}^{*}\)
34:endif
35:endif
36:if\(X_{1}^{*}\
otin Z^{+},X_{2}^{*}\
otin Z^{+}\)then
37:if\(f\left(X_{2}^{*}\right)\) or \(\left(X_{2}^{*}\right)<\mathit{LB}\)then
38:Cut P1(P2), for P2(P1): repeat Step 3-Step 5
39:endif
40:endif
41:endwhile
42:Step8 Termination condition:
43:ifT=100, Or \(\frac{\left\lfloor\mathit{UB}-\mathit{LB}\right\rfloor}{\mathit{LB}}<\varepsilon\)then
44:STOP,\(f\left(X^{\text{best}}\right)=\mathit{LB}\)
45:endif
```  
**Algorithm 1** Branch-and-cut algorithm.