Is there a name for this variation of the assignment problem?

Question

I'm given two matrices:

$A$, an $n\times n$ adjacency matrix of a graph. The graph is unweighted, undirected and has no self-edges or multi-edges.

$X$, an $n\times n$ symmetric matrix of edge weights for items $x_1,\dots,x_n$ where entry $(i,j)$ denotes the edge weight between item $x_i$ and $x_j$, if that edge eventually exists. Edge weights are real numbers between -5 and +5.

The items $x_1,\dots,x_n$ are assigned to exactly one node each, the objective being to assign items to nodes to maximise the total sum of edge weights.

I thought it might be a variation of the assignment problem, but with the cost of assignments dependent on the graph structure I'm uncertain how this would be formulated. So far I've tried a greedy heuristic algorithm which randomly assigns items to nodes, swaps the nodes which most increases the total edge weight sum, and repeats until no swap will increase the sum further. This frequently gives far from optimal solutions though.

Is there a name for this sort of problem, and what might be the best solution method?

Answer 1

It is the quadratic assignment problem. A survey is given here https://www.sciencedirect.com/science/article/abs/pii/S0377221705008337.

A formulation would be:

Decision variables $ y_{ij} \in \{0,1\}$ that is 1 if $x_i$ is assigned to node $j$. The objective is then $\sum_{i,j,k,p} A_{k,p}X_{i,j}y_{ik}y_{jp}$, where $A_{k,p}$ is 1 if the edge between $k$ and $p$ exists, otherwise zero and $X_{i,j}$ is the cost between $x_i$ and $x_j$.

And you need the assignment constraints. $\sum_i y_{ij} = 1\quad\forall j$ and $\sum_j y_{ij}= 1\quad\forall i$.