  


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 branchandbound algorithm that obtains the first optimal solution of the 1norm version of Steinberg's problem. Keywords: quadratic assignment problem, branchandbound Category 1: Integer Programming (01 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  