0

We want to connect $n$ modules by wires. The distance between two position $i, k$ is $a_{ik}$. $b_{jl}$ is the number of connections between module $j$ and $l$. Now we're looking for an assignment of the modules to their positions so that the total wire length is minimal.

I need to formulate a models that represents this problem, $\min f(x) = ?$.

How could this be done? The total wire length is minimal iff the number of connections and the sum of the length of connections is minimal. How could I express this? Thanks!

illuminatitruthseeker
  • 561
  • The problem is a quadratic assignment problem (QAP), and the objective function is the sum of the distances between pairs of modules weighted by the number of connections between them. The mathematical formulation is $\min f(x) = \sum_{i,j,k,l} a_{ik} b_{jl} x_{ij} x_{kl}$ where $x_{ij}$ is a binary variable indicating if module $i$ is assigned to position $j$. – rumathe Mar 20 '23 at 21:36
  • Thank you! Does the sum count $i,j,k,l$ at the same time like all those varibales are increased by 1 at the same time or are these 4 separate sums? – illuminatitruthseeker Mar 20 '23 at 21:40
  • It is equivalent to four separate sums nested within each other – rumathe Mar 21 '23 at 08:05

0 Answers0