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
  • 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$
    – Ggouvine
    May 25, 2020 at 8:00

1 Answer 1

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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