Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

The reformulation-linearization technique (RLT), introduced in [W.P. Adams, H.D. Sher-ali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10):1274{1290, 1986], provides a way to compute linear program-ming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry in the original problem data, it is sometimes possible to compute level two RLT bounds with additional linear matrix inequality constraints. As an illustration of our methodology, we compute the best-known bounds for certain graph partitioning problems on strongly regular graphs