Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems |
| |
Authors: | Etienne de Klerk Marianna E -Nagy Renata Sotirov Uwe Truetsch |
| |
Institution: | 1. Department of Econometrics and OR, Tilburg University, The Netherlands;2. Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands |
| |
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. |
| |
Keywords: | Reformulation&ndash linearization technique Sherali&ndash Adams hierarchy Quadratic assignment problem Standard quadratic optimization Semidefinite programming |
本文献已被 ScienceDirect 等数据库收录! |
|