(this is the core of the BF memory optimizer challenge.)
(At the moment I still need to make some test cases; however you can still review the rest of the challenge.)
note: This problem is reducible from Simple Max Cut, therefore it's NP-complete. (https://doi.org/10.1016/0304-3975(76)90059-1)
note: While I did get a bunch of test cases from this site, I'm not sure how can I write a reasonable algorithm to compete with...
Proof
(actually this is not part of the sandbox challenge, but I'll post it here because it's related)
First, for convenience, assume that the problem is represented by a undirected graph, where the number of rows/columns of the matrix is equal to the number of nodes, and the corresponding weight is the sum of the value of the edges connecting the corresponding two nodes.
With that representation, the value to be minimized is the sum of the product of the edge lengths and the edge weights, with the graph nodes embedded into the point \$ 1, 2,\ldots, |V| \$.
From a Simple Max Cut problem of the form:
Given \$ n \$ variables \$ x_1, x_2,\ldots, x_n \$, maximize the value of \$ \sum_{i=1}^m [a_i \ne b_i] \$, where each of \$ a_i, b_i \$ represents either a variable or its negation.
It can be transformed to an instance of this problem:
First, construct \$ 2n \$ nodes on a graph, denoted \$ p_1, p_2,\ldots, p_n, q_1, q_2,\ldots, q_n \$. Let \$ a \$ be some positive integer.
Connect those vertices:
- \$ p_1 \$ and \$ q_1 \$, with cost \$ 2n^2 a \$,
- the 4 pairs of vertices \$(p_1, p_i),(p_1, q_i),(q_1, p_i),(q_1, q_i)\$ with cost \$ (n+1-i) a \$, for each \$ i=2, 3,\ldots, n \$,
- and some other edges with small weights (the sum of their weights should be less than \$a\$ -- (1)) that mainly does not affect the optimal configuration.
The sum of the edge weights (except the first one) is \$ 4 ((n-1)+(n-2)+\ldots+1)a=2n(n-1)a \$.
The edge between \$ p_1 \$ and \$ q_1 \$ has a weight larger than the sum of all the others, it's obvious to see that in the optimal (minimum cost) configuration, these two must be adjacent.
Then, regardless where those 2 vertices are placed, the \$ i \$'th smallest distance-pair to those are at least the \$ i \$'th value in the sequence are
$$(1, 2),(1, 2),(2, 3),(2, 3),(3, 4),(3, 4),\ldots,(n-1, n),(n-1, n)$$
.
And by the rearrangement inequality, it's optimal to place the weight so that the vertices with the smaller edge-weight to \$ p_1, q_1 \$ are placed further from the vertices. Therefore the only optimal placement is
$$z_n, z_{n-1}, \ldots, z_2, z_1, z_1, z_2, \ldots, z_{n-1}, z_n$$
where each \$ z_i \$ is either \$ p_i \$ or \$ q_i \$ (\$1 \le i \le n\$).
Encode the condition "vertex \$ i \$ is on the left side of the cut" by "\$ p_i \$ is to the left of \$ q_i \$ in the permutation". (2)
Assuming that the edge weights are allowed to be fractional.
For each condition (in the Simple Max Cut problem) that "there's an edge between vertices \$u\$ and \$v\$ (\$ u\le v \$)", add an edge between \$ p_u \$ and \$ q_v \$ with weight \$\frac 1 {2u-1}\$ to this problem.
The weight of this edge can either be \$ u-v \$ or \$ u-v+(2u-1)\$ in the configuration that minimizes the total weight of the edges constructed in the previous section.
Therefore, if the vertices \$ u \$ and \$ v \$ are on different sides of the cut (according to the encoding (2)), the total weight is decreased by \$ 1 \$ if \$ u \$ and \$ v \$ are on different sides; and the configuration with the minimum weight is exactly the one with maximum number of edges cut.
However, in the actual problem edge weights must be an integer. We replace each edge weight \$\frac 1 {2u-1} \$ by \$\lceil\frac c {2u-1}\rceil \$, where \$ c=2nm\$.
Because there are \$ m \$ edges in total, if the sum of any \$ k-1 \$ increment values \$\lceil\frac c {2u-1}\rceil (2u-1) \$ is strictly less than the sum of any \$ k \$ increment values, for \$1\le k\le m \$, then the optimal sum is also the maximum cut.
Observe that because \$ c=2nm \$ and \$ x\le 2n-1 \$, each increment value must be between \$ 2nm \$ (inclusive) and \$ 2nm+2n-1 \$ (exclusive). Therefore the maximum sum of \$ k-1 \$ values is \$ (2nm+2n-2)(k-1) \$, which is less than the minimum sum of \$ k \$ values \$ 2nmk \$ when \$ 1\le k\le m \$.
The sum of all those does not exceed \$ \lceil \frac {2nm}{1} \rceil m \$. Therefore if \$ a \$ is chosen to be \$ 2nm^2+1 \$, then the condition (1) is satisfied.
Minimum cost matrix permutation
fastest-code (or optimized-output? Obviously the latter would be more useful in practice code golf)
Given a matrix \$w\$ in \${\mathbb N_0}^{n\times n}\$, define the symmetric matrix \$d\$ in \${\mathbb N_0}^{n\times n}\$ by the formula \$d_{i,j}=\left| i-j \right|\$, find a permutation matrix \$P\$ such that the sum of elements in the matrix \$(P^{\mathsf T} \cdot w \cdot P ) \,\odot\,d\$ (where \$\odot\$ denotes the Hadamard product/element-wise product) is smallest.
The result will be the mean (TODO: median? mean of the 50% maximum? mean result/naive ratio?) of the score over these test cases, for as long as you can run your program.