Uwe Truetsch

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

  • Etienne de Klerk
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags ,

    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

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    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