# Optimizing Rural Highway Maintenance Scheme with Mathematical Programming
## 3 A Single-Level Mathematical Programming Model  
In the previous section, we discussed the development of a bi-level mathematical programming model tailored specifically to rural highway maintenance management. However, due to the inherent complexity and NP-hardness of bi-level models, solving them for large-scale problems within a reasonable time frame is generally not feasible. To address this challenge, we reformulate the bi-level model into a single-level mathematical programming model that can be effectively solved by commercial solvers. This reformulation involves the introduction of binary variables and linearization techniques, which transform the problem into a mixed-integer linear programming (MILP) problem. The cost of the road segments that a route passes through is added to form a route cost function:  
\[c_{p}^{w}=\sum_{a\in A}\delta_{a,p}^{w}t_{a},\;p\in R_{w},\;w\in W \tag{8}\]  
where \(\delta_{a,p}^{w}=1\) if route \(p\) travels through the road segment \(a\); otherwise, \(\delta_{a,p}^{w}=0\). As per the traditional illustration of the user equilibrium (UE) principle in traffic assignment problems (TAPs) [39], we are aware that the system of inequalities can be derived from the lower-level model:  
\[\left\{ \begin{array}{l}L\cdot\sigma_{p}^{w}+\varepsilon\leq f_{p}^{w}\leq M \cdot(1-\sigma_{p}^{w})\\ L\cdot\sigma_{p}^{w}\leq c_{p}^{w}-\pi^{w}\leq M\cdot\sigma_{p}^{w}\\ \epsilon_{p}^{w}-\pi^{w}\geq 0\\ \sigma_{p}^{w}\in\{0,1\}\\ \forall p\in R_{w},\;w\in W\end{array} \right. \tag{9}\]  
where \(L\) and \(M\) are parameters that are small and large enough, respectively; the variable \(\sigma_{p}^{w}\) is a binary decision variable that is used for reformulation. However, due to the non-linear variable \(c_{p}^{w}\), the above system of inequalities (9) transforms the mathematical programming into mixed integer non-linear programming (MINLP), which is still challenging to solve. Observing that \(c_{p}^{w}\) is the only non-linear variable in the above model, we use a linearization approach to divide the feasible domains of \(c_{p}^{w}\) into many small areas. In every area, the variable becomes a linear one. In other words, the system of inequalities (9) is linearized as follows:  
\[\left\{ \begin{array}{l}L\cdot\zeta_{a,n}\leq x_{a}-K_{a,n}\leq U\cdot(1-\zeta _{a,n})-\varepsilon\\ \zeta_{a,n}=\zeta_{a,n+1}-\zeta_{a,n}\\ L\cdot(1-\zeta_{a,n})\leq t_{a}-a_{a,n}x_{a}\leq U\cdot(1-\zeta_{a,n})\\ \zeta_{a,n}\in\{0,1\}\end{array} \right. \tag{9a}\]  
where \(K_{a,n}\) is a known coefficient, since it is pre-specified; the variable \(\zeta_{a,n}\) is a binary decision variable that is used for reformulation. Thus, the revised single-level model is provided by  
\[\text{min}Z=\sum\limits_{a\in A}x_{a}t_{a} \tag{10}\]  
\[\left\{ \begin{array}{c}\sum\limits_{a\in A^{\prime}}u_{a}\leq V\\ u_{a}=0,\ a\in A\smallsetminus A^{\prime}\\ u_{a}\in\{0,1\},\ a\in A^{\prime}\end{array} \right. \tag{11}\]  
\[\left\{ \begin{array}{c}L\cdot\xi_{a,n}\leq x_{a}-K_{a,n}\leq U\cdot(1-\zeta_ {a,n})-\varepsilon\\ \zeta_{a,n}=\zeta_{a,n+1}-\zeta_{a,n}\\ L\cdot(1-\zeta_{a,n})\leq t_{a}-a_{a,n}x_{a}\leq U\cdot(1-\zeta_{a,n})\\ \zeta_{a,n}\in\{0,1\}\end{array} \right. \tag{12}\]  
\[\sum\limits_{p\in R_{w}}f_{p}^{w}=q_{w},\ \forall w\in W \tag{13}\]  
\[x_{a}=\sum\limits_{w\in W}\sum\limits_{p\in R_{w}}\delta_{a,p}^{w}f_{p}^{w},\ \forall a\in A \tag{14}\]  
\[f_{p}^{w}\geq 0,\ \forall p\in R_{w},\ \forall w\in W \tag{15}\]  
The NP-hard bi-level model, which is known for its complexity and challenging nature, has been successfully transformed into a mixed-integer linear programming (MILP) problem through the application of the model discussed earlier. This transformation is crucial as it enables the problem to be approached and solved by a wide range of commercial solvers, thereby facilitating its practical implementation. However, it is important to note that the linearization technique employed in this transformation also has a considerable effect on the computational efficiency.