Advanced Optimization Models for Bandwidth Provisioning and Routing in Fixed Microwave Backhaul Networks

This paper addresses the problem of determining bandwidth allocation and traffic routes in fixed microwave networks such that overall bandwidth cost is minimized while traffic demands are satisfied with a required reliability level. These networks exhibit high variability in link throughput as modulations schemes are adapted dynamically to ensure acceptable bit-error rate at the receivers according to external conditions such as the weather. First, we formulate an optimal optimization approach based on mixed-integer linear programming, which is subsequently reinforced by inserting problem-specific valid inequalities based on global network capacity to reduce the search space and eliminate the unfeasible bandwidth/modulation combinations, thus reducing the number of decision variables. Then, we introduce a Lagrangian-based heuristic that provides near optimal solutions while reducing drastically the computation time. In comparison to previous work, our experimental results show that our approaches are capable to solve large real-world network instances in an effective manner. Furthermore, the results evaluate the impact of reliability and transported traffic demands on bandwidth cost.