Solving quadratic assignment problems with algebraic symmetry via semidefinite programming
01 / 2010 - 12 / 2013
The quadratic assignment problem (QAP) is well known in operations research (mathematical programming) and arises from applications as diverse as electronic circuit testing and hospital facility location. It is also famously hard to solve QAP instances, even ones of moderate size. In this project we will revisit the possibility of solving QAP problems using semidefinite programming in a branch and bound setting. In particular, we will use modern techniques from algebraic combinatorics to exploit algebraic structures in the data where present.