Kth Optimal Solution of the Assignment Problem by Hungarian-Branching Hybrid Method

In real-life situations, in addition to an optimal solution, one may be required to find the Kth best solution, K ≥ 2, which usually is a difficult and computationally demanding problem. In this short communication, we develop a method to find the Kth best solution for an assignment problem by using the linear integer programming approach. This is done by generating an objective cut and adding it to the current optimal tableau and solve until the desired Kth optimal solution is obtained. The proposed method has the advantage that only one problem is solved at every stage or iteration. The assignment problem has real life application in logistics and transportation, workforce scheduling, resource allocation, project assignment, matching algorithms and sports scheduling.