New Classes of Unconstrained Permutation-Based Problems and Their Solutions

Three permutation-based matrix combinatorial sets were introduced: a) a matrix set of multipermutations of row entries; b) a matrix set of permutations of rows; c) a matrix set of multipermutations of rows and row entries. A polynomial (on the dimension of matrices) solvability of linear combinatorial optimization problems on these sets was justified. The connection between these problems with Linear Assignment Problems is established. Thus a class of polynomially solvable optimization problems is expanded remarkably. These results can be applied in different areas of Operations Research, such as Geometric Design and optimal management.