Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems
Etienne De Klerk (e.deklerkuvt.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.
Entry Submitted: 01/02/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|