Accelerating Dynamic Linear Assignment Problem solver using Primal Algorithms

The classical Linear Assignment Problem can be solved using established algorithms like Hungarian algorithm quite efficiently within linear time complexity. However, there are other classes of problems like resource capacitated assignment problems that uses Lagrangian relaxation schemes with branch and bound that require LAPs to be solved iteratively multiple times with minor variations on cthe cost matrix. The established methods for solving LAPs require them to re-solve each of the modified cost matrix from scratch. I built an algorithm that can outperform the established algorithms by leveraging the results of a previous iteration’s result to achieve results quicker.

Detailed Report

For an in-depth exploration of the algorithm, including methodologies and theoretical underpinnings, refer to the full report:

Performance Analysis

Discover the performance comparisons between the primal algorithm and the Hungarian algorithm across various matrix sizes and sparsity levels. Detailed results and analysis can be found at the link below: