Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems

E. de Klerk, M. Nagy, R. Sotirov, U. Truetsch

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)

Abstract

The reformulation–linearization technique (RLT), introduced in [Sherali, H. D., Adams. W. P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM Journal on Discrete Mathematics 3(3), 411–430], provides a way to compute a hierarchy of 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 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.
Original languageEnglish
Pages (from-to)488-499
JournalEuropean Journal of Operational Research
Volume233
Issue number3
Early online date12 Oct 2013
DOIs
Publication statusPublished - Mar 2014

Keywords

  • reformulation-linearization technique
  • Sherali-Adams hierarchy
  • quardratic assignment problem
  • standard quadratic optimization
  • semidefinite programming

Fingerprint Dive into the research topics of 'Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems'. Together they form a unique fingerprint.

  • Cite this