Content area
A number of algorithms exist to solve, or provide a near-optimal solution to, the multidimensional assignment problem. Despite the fact that the multidimensional assignment problem has existed for almost fifty years, quickly finding a good quality, near-optimal solution to the multidimensional assignment problem is still difficult. Solving large multidimensional assignment problems is difficult due to the total number of feasible solutions to be evaluated; the total number of feasible solutions for a 5x5x5x5x5 multidimensional assignment problem is 207,360,000. The number of feasible solutions grows exponentially as the number of dimensions increases.
Solving smaller multidimensional assignment problems by complete enumeration of all feasible solutions is possible, but for larger multidimensional assignment problems (with size and dimension equal to or greater than six) the time required for complete enumeration often exceeds the time available to compute a solution. Consequently many multidimensional assignment problem heuristic and metaheuristic algorithms have been developed in order to determine a good quality solution to the multidimensional assignment problem in a minimum or reasonable amount of time. Some of these algorithms utilize a neighborhood search in order to improve the quality of the starting solution. Searching a large neighborhood is desirable, because a better solution is more likely from searching a larger neighborhood, but searching a large neighborhood also requires additional time.
An improvement graph has been used to solve partitioning problems but has not been utilized to solve a multidimensional assignment problem. This work offers a new methodology to solve the multidimensional assignment problem that uses an improvement graph. By creating disjoint subsets of the multidimensional assignment problem data, using interpermutation exchanges and an improvement graph, and creating cyclic transfers, it is possible to quickly find a near-optimal solution to a multidimensional assignment problem.