On the SQAP-polytope

作     者：Jünger, M Kaibel, V 

作者机构：Univ Cologne Inst Informat D-50969 Cologne Germany Tech Univ Berlin D-10623 Berlin Germany 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2000年第11卷第2期

页      面：444-463页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：quadratic assignment problem symmetric model polyhedral combinatorics 

摘      要：The SQAP-polytope was associated to quadratic assignment problems with a certain symmetric objective function structure by Rijal (1995) and Padberg and Rijal (1996). We derive a technique for investigating the SQAP-polytope that is based on projecting the (low-dimensional) polytope into a lower dimensional vector-space, where the vertices have a more convenient coordinate structure. We exploit this technique in order to prove conjectures by Padberg and Rijal on the dimension of the SQAP-polytope as well as on its trivial facets.