The Steinberg Wiring Problem
N.W. Brixius (natbrmicrosoft.com)
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.
Entry Submitted: 10/24/2001
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|