Lagrangian Relaxation in Multidimensional Assignment) Apply the Lagrangian relaxation method to the multidimensional assignment problem of Example 10.7, in a way that requires the solution of 2-dimensional assignment problems. Derive the form of the corresponding subgradient algorithm
Example 10.7 In the assignment problems we have considered so far, we group the nodes of the graph in pairs. Multidimensional assignment problems involve the grouping of the nodes in subsets with more than two elements, such as triplets or quadruplets of nodes. For an example of a 3-dimensional assignment problem, suppose that the performance of a job j requires a machine m and a worker w, and that there is a given value ajmw corresponding to the triplet (j, m,w). Given a set of jobs J, a set of machines M, and a set of workers W, we want to find a collection of job/machine/worker triplets that has maximum total value.