# Difference between revisions of "Quadratic assignment problem"

Jump to navigation Jump to search

Author: Thomas Kueny, Eric Miller, Natasha Rice, Joseph Szczerba, David Wittmann (SysEn 5800 Fall 2020)

## Theory, Methodology, and/or Algorithmic Discussions

Joe Szczerba and Tom Kueny to provide.

## Example

Eric Miller to provide.

## Applications

Natasha Rice and David Wittmann to provide.

### The Backboard Wiring Problem

As the quadratic assignment problem is focused on minimizing the cost of traveling from one location to another, it is an ideal approach determining placement of components in many modern electronics. Leon Steinberg proposed a QAP solution optimize the layout of elements on a blackboard by minimizing the total amount of wiring required. In his paper Steinberg a backboard with a 9 by 4 array, allowing for 36 potential positions for the 34 components that needed to be placed on the backboard.

When defining the problem Steinberg states that we have a set of n elements

$E=\left\{E_{1},E_{2},...,E_{n}\right\}$ as well as a set of r points

$P_{1},P_{2},...,P_{r}$ where $r\geq n$ In his paper he derives the below formula:

$min\sum _{1\leq i\leq j\leq n}^{}C_{ij}(d_{s(i)s(j))})^{k}$ where

$C_{ij}$ represents the number of wires connecting components $E_{i}$ and $E_{i}$ $(d_{s(i)s(j))})$ is the length of wire needed to connect tow components if one is placed at $P_{\alpha }$ and the other is placed at $P_{\beta }$ 