Quadratic Assignment Problem

By Muhammad Al-Salamah

You want to design a circuit board which requires the placement of n electronic components in n positions. Let S to represent the set of electronic components and T the set of positions on the board. The electronic components have to be connected to each other by a series of wires. The board has to be designed with the minimum total length of wire used. Define the following: t_ik is the number of wires that must connect electronic component i to position k and d_jl is the distance between position j and position l on the board. Define the variable x_ij:

The best design of the board will be given by minimizing the objective function

The restrictions on the placement of the components are that each electronic component is assigned to one position and that each position is assigned only one electronic component. The constraints therefore are: