Search code examples
algorithmmatrixpermutationmathematical-optimization

Convert matrix to block matrix by permuting rows and columns

I have a rectangular matrix with n rows and m column. All entries of the matrix are natural numbers (including 0).

Among the m columns, I'm given some index, j (< m). I'd like the matrix to become a block matrix as shown below.

enter image description here

For the first i rows (we can choose any i <= n we want), every entry to the right of j should be 0. And for the next (n-i) rows, every entry to the left of index j (and including j) should be 0.

If this is impossible, the sum of the entries in the two shaded areas (dark grey) in the figure above should be as small as possible.

The only operations allowed on the original matrix are swapping rows and swapping columns. I'm interested in an efficient algorithm to achieve this.

Edit

Here is the CSV file for the original matrix (real world data from my application): https://github.com/ryu577/optimizn/blob/master/optimizn/ab_split/testing/arrs_orig.csv

The j is 25.

I have achieved a score of 561 on this matrix with simulated annealing. I would be interested to see if anyone can beat this.

Solution

  • Two practical approaches:

    1. Create an optimization problem that minimizes sum of squares of the corresponding coefficients in the target matrix, given two permutation matrices: the matrix C of dimensions mxm and matrix R of dimensions nxn. Add requirements RR^T=I and CC^T=I using Lagrange multipliers. Run optimization to find optimal C and R. Then add a regularizer to the target function that will turn those matrices in a proper permutation (e.g. 0s and 1s).
    2. Use genetic optimization.

    Neither guarantees optimal solution.