A heuristic for the time constrained asymmetric linear sum assignment problem

The linear sum assignment problem is a fundamental combinatorial optimisation problem and can be broadly defined as: given an $$n \times m, m \ge n$$ n × m , m ≥ n benefit matrix $$B = (b_{ij})$$ B = ( b i j ) , matching each row to a different column so that the sum of entries at the row-column intersections is maximised. This paper describes the application of a new fast heuristic algorithm, Asymmetric Greedy Search, to the asymmetric version ( $$n \ne m$$ n ≠ m ) of the linear sum assignment problem. Extensive computational experiments, using a range of model graphs demonstrate the effectiveness of the algorithm. The heuristic was also incorporated within an algorithm for the non-sequential protein structure matching problem where non-sequential alignment between two proteins, normally of different numbers of amino acids, needs to be maximised.