March 28, 2014 Andreas Lundell PhD theses

The quadratic assignment problem (QAP) is often referred to as a facility location problem where the goal is to determine the best placing of facilities on a predefined set of locations. As with many other combinatorial optimization problems, QAPs arise in a number of different fields. A few real world examples include: hospital layout planning, airport gate assignment, keyboard configurations and turbine balancing in power plants. The versatility of the fields of application where QAPs are found is one of the reasons why they are important to study. Despite its relatively old age, the QAP is a notoriously difficult problem and instances with only 30 locations are still unsolved using all the methods presented in the literature. In its normal form, the QAP is highly nonlinear with nothing but bilinear terms in the objective function.

My thesis is a summary of four papers. In the first three papers, reformulations for the QAP and a few techniques to improve them are presented. The objective function of the QAP is reformulated to a new form which then is discretized to a mixed integer linear programming formulation. In this way, some instances were solved to proven optimality for the first time ever. The fourth paper shows how the same reformulations can be applied to a multiechelon supply chain problem, in order to improve the model considerably.

The thesis can be downloaded here.