An approximate approach to the unsplittable flow edge load factor balancing problem with the Lagrangian relaxation

This study has focused on the UELB problem that aims at leveling the traffic load of a communication link in an information network by determining the path of a flow that minimizes the maximum load factor of the link. The UELB problem has been proved to be NP-hard, and an approximate solution method using the LP relaxation has been proposed to verify the results. This paper proposes another algorithm using the Lagrangian relaxation method in order to objectively evaluate the accuracy of the approximate solutions obtained so far. We have conducted comparison experiments with the method using LP relaxation. The result has demonstrated that the proposed algorithm has relatively higher computational complexity and taken a long time to calculate the solution because of using the subgradient method for the Lagrangian relaxation. In addition, it is indicated that both the conventional LP relaxation and the proposed algorithm are effective because they are close to the exact solution.