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 exact solution. The results showed that the proposed algorithm gradually improves the accuracy of the solution as the number of calculations of the subgradient method is increased. In addition, it was found that when Lagrangian relaxation is performed, it is better to apply LP relaxation at the same time. Conducting the relaxation at the same time will lead to a reduction in computation time.