April 25, 2014 Post doc researchers

I’m studying the Quadratic Assignment Problem (QAP) which is a famous NP- hard combinatorial problem. Many real world problems can be formulated as quadratic assignment problems.   These problems arise in economics, archaeology, electronics, facility layout and many more different fields of research.This is why the QAP is an important problem to study.  Some real-life examples:

• Backboard Wiring. QAPs are solved to minimize the total wiring between components on a backboard.
• Hospital Design. A QAP is solved to determine where to place the different wards in a hospital to minimize moving of the patients.
• Gate Assignment. At airports QAPs can be used to minimize the total amount passengers have to walk between gates.

The objective in the standard Koopmans-Beckmann form of the quadratic assignment problem is to minimize a sum of bilinear terms.  Many different formulations have been presented in the literature but still only a few problems of n>30 have been solved to optimality to this day (2). These larger instances have been solved using large computer grids and the solution times calculated on a single computer are in years. We have reformulated the problem to an exact discrete form that can be solved by general MILP solvers. This reformulation gives very good results and we have solved large instances from the online quadratic assignment problem library, QAPLIB (1), that have never been solved to proven optimality before. We have solved them on a single computer and still the running times are relatively short. Different heuristics work very well on these types of problems but give no information about the quality of the solution.  This is why it is important to study exact methods or tight lower bound calculations for the QAP.