A new family of facet defining inequalities for the maximum edge-weighted clique problem

被引：2
作者：
Fomeni, Franklin Djeumou [1 ,2 ]
机构：
[1] Polytech Montreal, Gerad, Montreal, PQ H3T 3A7, Canada
[2] Polytech Montreal, Dept Math & Ind Engn, Montreal, PQ H3T 3A7, Canada
来源：
OPTIMIZATION LETTERS | 2017年 / 11卷 / 01期
关键词：
Edge-weighted clique problem; Cutting planes; Separation algorithm; Integer programming; Boolean quadric polytope; Facet defining inequalities; QUADRATIC KNAPSACK-PROBLEM; ALGORITHMS; POLYTOPE;
D O I：
10.1007/s11590-016-1055-z
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these inequalities. The result of this paper may contribute to the development of more efficient algorithms for the maximum edge-weighted clique problem that use cutting planes.
引用
收藏
页码：47 / 54
页数：8
相关论文
共 20 条
12