A new semidenite programming relaxation for the quadratic assignment problem and its computational perspectives

Recent progress in solving quadratic assignment problems (QAPs) from the QAPLIB test set has come from mixed integer linear or quadratic programming models that are solved in a branch-and-bound framework. Semidenite programming bounds for QAP have also been studied in some detail, but their computational impact has been limited so far, mostly due to the … Read more

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. Sherali, 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 programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry … Read more