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

Abstract

 In real-life situations, in addition to an optimal solution, one may be required to find the K^th best solution, K ≥ 2, which usually is a difficult and computationally demanding problem. In this short communication, we develop a method to find the K^th 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 K^th 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.