In 1961 Leon Steinberg formulated a "backboard wiring" problem that has resisted solution for 40 years. Steinberg's wiring problem is to determine the locations of 34 computer components on a 4 by 9 grid so as to minimize the total length of the wiring required to interconnect them. The problem is an example of a quadratic assignment problem, or QAP. This paper gives an overview of solution approaches for QAP, and describes a branch-and-bound algorithm that obtains the first optimal solution of the 1-norm version of Steinberg's problem.
Citation
Dept. of Management Sciences, University of Iowa, October 2001.