## 5 Optimization Method
### Column-Generation Procedure  
The CG procedure uses the linear relaxation of problem (2)-(24), which is an LP problem. In the LP problem, the objective function and problem constraints are the same as in the original MILP problem. At the same time, the decision (binary) variables are relaxed and can take any value in the interval \([0,1]\). At the beginning of CG, the LP problem is initialized and solved (using an LP solver) assuming a small set of allowable paths \(\widetilde{\mathcal{P}}\subset\mathcal{P}\) representing the initial, feasible solution found using the greedy algorithm in Section 5.2. Set \(\widetilde{\mathcal{P}}\) is iteratively extended with new paths provided by CG. At each iteration, the search for such paths is performed by solving a pricing problem. The pricing problem concerns finding a new path \(p\), where \(p\in\mathcal{P}\) and \(p\
otin\widetilde{\mathcal{P}}\), for which its so-called reduced cost is positive (and the largest). When found, the new path (or paths) is included in set \(\widetilde{\mathcal{P}}\), and the LP problem is solved again; otherwise, the CG procedure terminates. The paths in set \(\widetilde{\mathcal{P}}\) are identified with variables \(x_{dfp}\), and each path \(p\in\widetilde{\mathcal{P}}\) is represented by a variable \(x_{dfp}\) in the LP model. To define the pricing problem and calculate the reduced cost of variable \(x_{dfp}\), we first formulate the constraint related to this variable in the problem dual to the LP relaxation. This constraint uses the dual variables specified on the LHS of constraints (10)-(16) and is the following:  
\[ \begin{gathered}\alpha^{\text{FH}}(f)\times\left(\lambda_{d}^{ \text{FH}}-\pi_{d0}^{\text{FH}}\right)-\\ \alpha^{\text{MH-eMBB}}(d,f)\times\mu_{d0}^{\text{DU-eMBB}}-\\ \alpha^{\text{MH-URLLC}}(d,f)\times\left(\mu_{d0}^{\text{DU-URLLC }}-\mu_{d0}^{\text{CU-URLLC}}\right)-\\ \sum_{c\in\mathcal{E}(p)}\left(H(d,f)\cdot\kappa_{e}+\sigma_{dfe} \right)\leq 0,\end{gathered}  \tag{25}\]  
\[\forall d\in\mathcal{D},f=\mathcal{F},p\in\mathcal{P}(d,f),\]  
where coefficients \(\alpha^{\text{FH}}(f)\), \(\alpha^{\text{MH-eMBB}}(d,f)\), and \(\alpha^{\text{MH-URLLC}}(d,f)\) activate/deactivate particular components of the constraint depending on the type of demand and flow of interest. Namely, \(\alpha^{\text{FH}}(f)=1\) if \(f\) is an FH flow, \(\alpha^{\text{MH-eMBB}}(d,f)=1\) if \(f\) is an MH flow of a demand belonging to an eMBB slice, and \(\alpha^{\text{MH-URLLC}}(d,f)=1\) if \(f\) is an MH flow of a demand belonging to an URLLC slice; otherwise, the coefficients take a value of 0. The LHS of (25) represents the reduced cost of primal variable \(x_{dfp}\). Let \(\lambda^{\text{FH}}\), \(\pi^{\text{FH}}\), \(\mu^{\text{DU-eMBB}}\), \(\mu^{\text{DU-URLLC}}\), \(\mu^{\text{CU-URLLC}}\), \(\kappa\), and \(\sigma\) be the vectors representing an optimal dual solution obtained for the current LP. Constraint (25) imposes that all the values of its LHS are non-positive for such an optimal dual solution. However, there may be paths outside of the set of paths \(\widetilde{\mathcal{P}}\) in the current LP that can have a positive reduced cost for this optimal dual solution. Recall that the problem dual to the primal minimization problem (such as the LP considered) is a maximization problem, and the values of the optimal primal and dual objectives are always equal. Therefore, adding the paths of a positive reduced cost to the problem can decrease the maximum value of the dual objective and, thus, decrease the minimum value of the primal objective (2), which is the optimization goal. As adding such paths into set \(\widetilde{\mathcal{P}}\) may be beneficial, the CG procedure aims to search for them.