Looking for an efficient way of maximising 'pair scores' for subset of 30 selected from 50 to 10 000 objects

Question

Context: I have a tiling program that uses a directed breadth first search algorithm. It is 'directed' by what I call 'pair scoring'. There are $N$ polyforms (pieces) used in the tiling. I have an $N\times N$ array with a score in every location. While tiling I seek to maximise the sums of pair scores of unused pieces. At the start I sum all the scores, find the mean score and subtract the mean from all scores so they sum to zero. As I tile I can find the new total just by adjusting the current total for the node by removing scores belonging to the last placed piece.

I generate the $N\times N$ 'pair score' array by tiling a small shape with around 6 to 10 pieces, for every tiling found I look at the border cells of every piece '$a$' in the tiling, and wherever it touches piece '$b$' I increment $[a,b]$ and $[b,a]$. And wherever it touches the edge of the shape I increment $[a,a]$.

This works fairly well, but I suspect that I could optimise the 'end game' further by encouraging a tendency to end with one of the 'local maxima', being the group(s) of pieces that 'score the best as a set'.

In order to know whether my algorithm is finding such maxima, I need to first find them myself so I know when the node scores are missing these maxima.

So my question is, how do I efficiently find the highest scoring sets of 1 through $M$ out of $N$ pieces, where $M$ ranges up to about 30 and $N$ up to 1000 or so?

There is some redundancy available in the array, I currently just repeat $[a,b]$ in $[b,a]$. I could use $[a,b]$ for the pair score when $a < b$ and $[b,a]$ for something else. I already use $[a,a]$ for keeping track of how many times piece a touches an edge square in a tiling of the smaller shape. I can adjust the importance of this edge score by using a simple 'edge score factor'.

It would be nice to have an algorithm that was fast enough to track these local maxima as they change due to pieces being used, without adversely impacting tiling speed too much. Then I would know pretty quickly that I had 'gone wrong' i.e. even though I had a nice high node score, I had used a set of pieces which would reduce my best possible end game, and could use that to direct the BFS in addition to the simple node score.

Or is it the case that the node score already gives me that?

Answer 1

The stated problem is equivalent to determine a maximimum weight general matching of fixed cardinality; that problem can be solved efficiently as indicated in the answer to complexity of finding optimal matchings of given fixed size.

If however only a small number $M$ of pairs with minimum weight-sum has to be determined from a vast number $N$ of individuals, the $O(N^3)$ time complexity can render the exact algorithm not usable and heuristics are needed.

There are many heuristics that can be envisaged; the simplest one being the greedy strategy of choosing as tne next pair the one with maximal weight and then remove its elements from the set of candidates.

A more elaborate heuristic based on vertex weights could be:

• determine vertex weights, that reflect the vertice's contribution to the edge weights
• select the $2M$ top ranked vertices $T\subset V$
• calculate the general maximum weight perfect matching $\mathfrak{M}_T$ of the subgraph induced by those $2M$ top ranked vertices
• define $U$ to be set of vertices that have the smaller label of the pairs that are adjacent to an edge in $\mathfrak{M}_T$
• determine the maximum weight maximal bipartite matching $\mathfrak{M}_{(U,\,V\setminus U)}$

explanations:

• to have the vertex weights reflect their contribution to edge weights, they are choosen so that summing over the weights of edges, that are adjacent to the same vertex, equals the weights of their adjacent vertices; those conditions result in a system of equations that is explicitly solvable.
• calculating $\mathfrak{M}_T$ only yields a lower bound on the optimal solution; an illustrative situation is a set of points chosen from a closed disk, with sufficiently many points on the boundary and we want find the $M$ disjoint edges with maximal length sum; it is clear the edges will connect points on the boundary, but choosing $2M$ points from the boundary is only a necessary criterion for finding $M$ approximately antipodal pairs.
• The construction of the bipartite matching $\mathfrak{M}_{(U,\,V\setminus U)}$ from the edges of $\mathfrak{M}_T$ guarantees that the edge set of the bipartite matching contains the edges of $\mathfrak{M}_T$ and thus $\mathfrak{M}_{(U,\,V\setminus U)}$ is at least as good.

this answer is admittedly a bit sketchy, but a more specific description can be provided.