Local search methods for a column permutation problem for the binary matrix

The iterative local search methods for the column permutation problem for the binary matrix are developed and studied. It is known that the problem is NP-hard in the strong sense, and for the broad class of polynomial time approximation algorithms the relative deviation from the optimum may be arbitrary large in the worst case. In this paper we show that the iterative local search methods can find the global optimum or near optimal solution quickly if the number of columns and the number of rows of the matrix are 100 at most.