Peter M. Hahn
     Adjunct Associate Professor of Systems Engineering

    Contents

   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

     Back to top

Biographical Information

   Peter Hahn C.V.

     Back to top

Contact Information

     Electronic mail address: hahn@seas.upenn.edu

     Web address: http://www.seas.upenn.edu/~hahn/

     Office phone: (215) 546-3413

     Back to top

Research Interests

     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 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

   Real size16 Q3AP instance
            Download:   qaptest.data.gz

     Back to top

     Last Revised:  Aug 30, 2008