Department
of Electrical and Systems Engineering
Biographical
Information
Contact
Information
Research
Interests
The
Quadratic Assignment Problem
Department
of Electrical and Systems Engineering
Biographical
Information
Contact
Information
Research
Interests
The
Quadratic Assignment Problem
Department of Electrical and Systems Engineering
Address:
Room 203 Moore Building, 200 S. 33rd Street, Philadelphia, PA 19104-6314
Home office:
2127 Tryon Street, Philadelphia, PA 19146-1228
Electronic mail address: hahn@seas.upenn.edu
Web address: http://www.seas.upenn.edu/~hahn/
Office phone: (215) 546-3413
Fax phone: (215) 546-4043
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.
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
facilities.
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.
QAP Publications:
"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)
Download: Paper
"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)
Download: Paper
"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)
Download: Paper
"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.
Download: Paper
"Tree Elaboration
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
"A Branch-and
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).
Download: Paper
"Branching
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).
Download: Vu-graphs
"Practical
Aspects of Calculation of Dual Procedure Bounds for the Quadratic Assignment
Problem," (invited) CO98 International Symposium on Combinatorial Optimization,
Brussels, April 15 1998.
Download: Vu-graphs
"Lower Bounds
for the Quadratic Assignment Problem Based on a Dual Formulation," Operations
Research, Vol 46, No. 6, Nov-Dec 1998.
(co-author: T. Grant).
Download: Paper
"A Hospital Facility
Layout Problem Finally Solved", Hahn, P. and Krarup, J., Journal of
Intelligent Manufacturing, Vol 12, No. 5/6, Oct. 2001.
Download: Paper
"Minimization
of Cost in Assignment of Codes to Data Transmission", University of
Pennsylvania, Electrical Engineering Department
Dissertation, August 1968.
Download: Paper
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.
Download: Paper
File for Van-Dat Cung
Download: qaptest.data.gz
Last Revised: Feb 1, 2008