Multi-dimensional Assignment

The Multi-dimensional Assignment Problem (MAP) is a generalization of a Linear Assignment Problem (LAP) with more than two dimensions. it is NP-Hard for the number of dimensions greater than 2. A dual ascent based approach is proposed as the lower bounding scheme and a Shortest path + Ranked assignment scheme is applied for the gap closure, to obtain optimal (and integral) solutions to MAP.  More information can be found in our papers [1], [3].