首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号