Optimization Online


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

Etienne De Klerk (e.deklerk***at***uvt.nl)
Marianna Eisenberg-Nagy (m.e.nagy***at***cwi.nl)
Renata Sotirov (r.sotirov***at***uvt.nl)
Uwe Truetsch (u.truetsch***at***uvt.nl)

Abstract: 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 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.

Keywords: reformulation-linearization technique, Sherali-Adams hierarchy, quadratic assignment problem, standard quadratic optimization, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming

Citation: Preprint, Tilburg University, The Netherlands, December 2011.

Download: [PDF]

Entry Submitted: 01/02/2012
Entry Accepted: 01/02/2012
Entry Last Modified: 03/12/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society