The constant objective value property for multidimensional assignment problems

An instance of a combinatorial optimization problem is said to have the constant objective value property (COVP) if every feasible solution has the same objective function value. In this paper our goal is to characterize the set of all instances with the COVP for multidimensional assignment problems.Our central result deals with planar dd-dimensional assignment problems. We show that such constant objective value instances are characterized by so-called sum-decomposable arrays with appropriate parameters. This adds to the known result for the axial dd-dimensional case.