Imagine I have given a $n \times n$ matrix $A:=[a_{i,j}]_{i,j \in \{1,...,n\}}$ of values and I want to have the sum as shown here:
$$\sum_{i\leq j}a_{ij}$$
which just corresponds to the sum of the upper triagle, so e.g. if $A=\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$ it corresponds to the sum $1+2+3+5+6+9=26$
Now I want to change the order of the elements in order to maximize the score, i.e. if I change element 2 with element 1 it corresponds to changing the column 2 with column 1 and the row 2 with row 1 which would be equal to:
$$\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}\to \begin{pmatrix} 2 & 1 & 3 \\ 5 & 4 & 6 \\ 8 & 7 & 9 \end{pmatrix} \to \begin{pmatrix} 5 & 4 & 6 \\ 2 & 1 & 3 \\ 8 & 7 & 9 \end{pmatrix}=:\tilde{A}$$
and the resulting sum would be $5+4+6+1+3+9=28$
Now I want to maximize the sum, so I want to flip rows and columns in order to find the maximum sum of the elements but I can't find a connection to a problem where there is already a solution;
I can display the problem as a graph: Then $a_{ij}$ can correspond to the weight of the edge from $i$ to $j$ and $a_{ii}$ is the weight of an edge from vertex $i$ to itself. Since the diagonal entries always stay on the diagonal and hence do not influence the maximality of the sum we can also set them all equal to zero so we do not have edges from a vertex to itself.
I then look for the permutation $\pi$ where the sum of the edge weights is maximized, only considering the edge weights $a_{ij}$ where $i<j$
Now I am particularly interested in the following:
- Is this problem NP-complete? I thought of adapting this problem to the Traveling Salesmen Problem because I think the problem is similar and should be NP-complete but I cant transform it yet
- What would be a smart solution to solve the problem without checking all $n!$ permutations?
Update: I tried a branch-and-bound algorithm as it was suggested:
I calculated an example; Imagine we have 4 vertices; Then our tree is given by:
Now assume our matrix is very simple; We have only 2 values: $0<a<b$ and the matrix is given by $a_{31}=b$, $a_{13}=a$ and for all other entries $a_{ij}=b$ if $i<j$ and $a_{ij}=a$ if $i>j$.
Now I start with k=2 meaning I check the first edges; If $a_{ij}<a_{ji}$ I can cancel the braches where the first and second vertices are $i$ and $j$; This means that the first vertex can't be $4$ because no matter what the second vertex is, we always get a higher score when flipping them; Also these combinations are not possible: $(1,3)$, $(2,1)$ and $(3,2)$; This leads to the reduced tree:
Now I go on to the next step and looking at edges one level lower: The permutation: 1->4->2 is not possible because 1->2->4 is still in the tree; For example, however, 1->4->3 is not possible to cut because we do not have 1->3->4 in the tree anymore (in this case it would be of course possible but I cant generally assume that) Also I can cut off 2 ->4 ->3 because we still have 2 ->3 ->4 in the tree and 3->4->1 because we have 3->1->4 So the reduced tree will be:
Now finally we will look at the lowest layer. 1->2->4->3 is not possible because we have: 1->2->3->4; Also not possible: 2->3->4->1 and 3->1->4->2;
So the final tree is:
So I was able to reduce the set of 4!=24 permutations to 6 permutations;
Is this how you meant it? Was it correct when I said "For example, however, 1->4->3 is not possible to cut because we do not have 1->3->4 in the tree anymore (in this case it would be of course possible but I cant generally assume that)"?
Your problem is NP-hard.
Suppose that the input matrix is the adjacency matrix of a directed graph, with $a_{ij} = 1$ whenever there is an edge from $i$ to $j$ and $a_{ij} = 0$ otherwise. In this case, we want to order the vertices such that as many of the $1$'s of the matrix end up in the upper triangle.
This is equivalent to finding a minimum feedback arc set of the graph: the minimum set of edges to delete so that the graph becomes acyclic. For the adjacency matrix of an acyclic graph, we can find a topological sort of the vertices that puts all the $1$'s in the upper triangle; so the minimum feedback arc set tells us the fewest number of $1$'s we're forced to leave in the lower triangle.
Unfortunately, the feedback arc set problem is NP-complete.
We can think of the general problem as being a similar problem, but about weighted complete directed graphs; equivalently, weighted tournaments. In this case, the optimal ordering of the indices is called a median order of the tournament. The problem obviously gets no harder when we allow arbitrary weights, but here are some papers: 1, 2. If you have access to them, they basically tell you that there's no good methods, but here are some that are least bad.
Basically, the strategy they employ is a branch-and-bound algorithm. All $n!$ orderings of the indices of your matrix can be thought of as leaves of a tree where you fix the positions of the indices one at a time. So at the top node, no positions are fixed. It has $n$ children based on which row/column we make the first one; then each of those has $n-1$ children based on the second row/column, and so on.
With branch-and-bound, we explore the most promising branches of the tree first, and use those to eliminate other branches without looking at them. If you have a particular ordering of the matrix, with a given upper triangle sum, and you're looking at a partial solution with the first $k$ rows fixed, if those $k$ rows have already made the triangle sum guaranteed to be smaller than your particular solution, no matter how the rest is filled, we can discard that partial solution.
Another paper 3 gives a randomized algorithm for the zero-one case (the feedback arc set problem) in particular.