of Electrical and Systems Engineering
The Quadratic Assignment Problem
Department of Electrical and Systems Engineering
Room 203 Moore Building, 200 S. 33rd Street, Philadelphia, PA 19104-6314
2127 Tryon Street, Philadelphia, PA 19146-1228
Back to top
Peter Hahn C.V.
Back to top
Electronic mail address: firstname.lastname@example.org
Web address: http://www.seas.upenn.edu/~hahn/
Office phone: (215) 546-3413
Back to top
Postal Systems: Address and character
recognition techniques, OCR technology as applied to U.S. mail address
reading, US Postal Service sorting and processing systems and US address directories. Research on hand print
and cursive script word recognition. Bulk mail center (BMC) network transportation and logistics.
Operations Research: Technology needs
assessment, technology development planning, system survivability and
vulnerability analyses, commonality and cost benefit analyses and communication versus processing trades.
Research into combinatorial optimization including development of a state-of-the-art branch-and-bound
enumerative method for solving large Quadratic Assignment Problems.
Communication Analysis and Simulation:
Development of computer models for performance analysis and
simulation of satellite communication systems. Linear and non-linear systems analysis, digital signal processing,
communication theory and numerical analysis. Development of an importance sampling technique for the
evaluation of bit error rate in high-performance digital communication systems.
Communication Networks: Design and development
of communications switching systems, including hardware and
software. Design and optimization of voice, data and packet switching communication networks.
Back to top
The Quadratic Assignment Problem (QAP)
The QAP covers a broad class of problems that
involve the minimization of a total pair-wise interaction cost among N
These problems include finding the assignment of factories to fixed locations which minimizes transportation cost and the location
of sub-assemblies on a chassis in order to minimize the length of interconnecting wiring. The Koopmans-Beckman version of the
problem can be stated with reference to a practical situation where it is desired to locate N facilities among N fixed locations, where
for each pair of facilities (i,k) a certain flow of commodities f(i,k) is known and for each pair of locations (j,n) a corresponding
distance d(j,n) is known. The two-way transportation costs between facilities i and k, given that i is assigned to location j and k is
assigned to location n, are f(i,k)·d(j,n) + f(k,i)·d(n,j) . The objective is to find an assignment minimizing the sum of all such
transportation costs. In the general case of the QAP, the cost of transportation between facilities is known but is not decomposable
into a product of a flow and a distance matrix.
"The Multi-Story Space Assignment Problem," accepted for publication in the Special Issue of Annals of Operations Research on Cutting, Packing and Space Allocation.
(co-authors: J.M. Smith, and Y.-R. Zhu)
"An algorithm for the generalized quadratic assignment problem," Computational Optimization and Application, Vol. 40 2008, No. 3, pp 351-372.
(co-authors: B.-J. Kim, M. Guignard, J.M. Smith, and Y.-R. Zhu)
"A Study of Quadratic
Assignment Problem Instances that are Difficult for Meta-heuristic
Methods," The Annals of Operations Research,
Integer Programming: State of the Art and Recent Advances, Vol. 139, 2005, pp 65-94.
(co-authors: Zvi Drezner and Eric Taillard)
"A Lower Bound
for the Quadratic Assignment Problem Based on a Level-2 Reformulation-
Linearization Technique", University of Pennsylvania, Systems Engineering
Department Report, 2001.
(co-authors: W.L. Hightower, T.A. Johnson, M. Guignard-Spielberg, C. Roucairol.
Strategies for Branch-and-bound Solution of the Quadratic Assignment Problem,"
Yugoslav Journal of Operations Research, Vol. 11 2001, No. 1, pp. 41-60. Also
presented at the Discrete Optimization ∆99 conference at RUTCOR, New Brunswick,
NJ, July 30, 1999.
Download: Paper Vu-graphs
Bound Algorithm for the Quadratic Assignment Problem based on the Hungarian
Method," European Journal of Operational Research, August, 1998. (co-authors,
N. Hall, T. Grant).
Strategies for a Quadratic Assignment Problem Branch and Bound Algorithm,"
(invited) INFORMS∆98, Montreal, April 26-29, 1998. (co-authors, W. Hightower
and T. Johnson).
Aspects of Calculation of Dual Procedure Bounds for the Quadratic Assignment
Problem," (invited) CO98 International Symposium on Combinatorial Optimization,
Brussels, April 15 1998.
for the Quadratic Assignment Problem Based on a Dual Formulation," Operations
Research, Vol 46, No. 6, Nov-Dec 1998.
(co-author: T. Grant).
"A Hospital Facility
Layout Problem Finally Solved", Hahn, P. and Krarup, J., Journal of
Intelligent Manufacturing, Vol 12, No. 5/6, Oct. 2001.
of Cost in Assignment of Codes to Data Transmission", University of
Pennsylvania, Electrical Engineering Department
Dissertation, August 1968.
Y-R Zhu,"Recent Advances and
Challenges in the Quadratic Assignment and Related Problems," University of
Pennsylvania, Electrical and Systems Engineering Department
Dissertation, August 2007.
Real size16 Q3AP instance
Back to top
Last Revised: Aug 30, 2008