6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It seems to be a variation of the quadratic assignment problem, with the weights between locations restricted to 0 and 1. It is difficult to solve using mathematical formulations but many heuristics have been proposed. $\endgroup$ – Gabriel Gouvine May 25 at 8:00
8
$\begingroup$

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.