The Steinberg Wiring Problem

N.W. Brixius (natbrmicrosoft.com)
K.M. Anstreicher (kurt-anstreicheruiowa.edu)

Abstract: 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.

Keywords: quadratic assignment problem, branch-and-bound

Category 1: Integer Programming (0-1 Programming )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Dept. of Management Sciences, University of Iowa, October 2001.

Download: [Postscript]

Entry Submitted: 10/24/2001
Entry Accepted: 10/25/2001
Entry Last Modified: 10/25/2001

Modify/Update this entry