Approaches to Obtain a Large Number of Ranked Solutions to 3-Dimensional Assignment Problems

Abstract

A generalized 3-dimensional assignment problem is a decision-making process that involves allocating limited resources to a set of tasks over time, where the objective is to optimize a cost function subject to a set of generalized assignment constraints. The 3-dimensional (3-D) assignment problems are known to be NP-hard. In this paper, we propose a novel approach to efficiently solve an m-best 3-D assignment problem with non-unity right-hand side constraints (also referred to simply as 3-D assignment problem), where m may be large (as many as 10⁴ solutions), by decomposing it into two sequential phases. In phase I, we partition the original problem space into a series of subproblems via Murty’s m-best search space decomposition procedure. Modifications previously proposed in the literature for the 2-dimensional (2-D) assignment problem are applied to optimize the search space decomposition for the 3-D assignment problem. In phase II, we solve each subproblem by using Lagrangian relaxation and solving the 3-D assignment problem as a combination of relaxed 2-D assignment problems and 2-D transportation problems. The 2-D assignment problem is solved by the JVC or auction algorithms, and the 2-D transportation problem is solved by the simplex-based transportation, Transauction or RELAX-IV algorithms. The sequence of relaxed 2-D problems are interchangeable, while adhering to the relaxed constraints. We validate and compare the performance and utility of the proposed algorithms and search space decomposition optimizations via extensive numerical experiments. Overall, the fully optimized algorithm took less than 50 seconds, on average, to obtain 10⁴solutions for a tensor of dimension 30 x 30 x 8.