Quadratic Assignment Polytopes

In this chapter we present various results and partial results on the facial structure of the quadratic assignment polytope QAP _n and its symmetric relative, the polytope SQP _n . We address primarily the questions of finding the affine hull and the dimension of the respective polytopes, but give also some valid inequalities for QAP _n . Some of these problems are left open and suggested in the form of conjectures for future work on this difficult, but interesting class of combinatorial optimization problems.