University of Twente Student Theses

Login
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.

Comparison of mixed-integer linear programming formulations for the quadratic assignment problem

Scheppink, J.L.C. (2025) Comparison of mixed-integer linear programming formulations for the quadratic assignment problem.

[img] PDF
1MB
Abstract:The quadratic assignment problem is a well-known challenge in combinatorial optimization. One approach to solving this problem is through linearization, where the quadratic formulation is reformulated as a mixed-integer linear program. In this paper, six linearizations from the literature are studied. For each formulation, we consider its linear programming (LP) relaxation. In addition, we execute theoretical strength comparisons between the LP relaxations. Computational experiments are performed on several instances to evaluate the practical performance of the LP relaxations. The resulting LP bounds provide insight into the strength of the LP relaxations.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:https://purl.utwente.nl/essays/107662
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page