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 条
  • [1] Solving the maximum edge weight clique problem via unconstrained quadratic programming
    Alidaee, Bahram
    Glover, Fred
    Kochenberger, Gary
    Wang, Haibo
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (02) : 592 - 597
  • [2] Exact solution of the Quadratic Knapsack Problem
    Caprara, A
    Pisinger, D
    Toth, P
    [J]. INFORMS JOURNAL ON COMPUTING, 1999, 11 (02) : 125 - 137
  • [3] A CUTTING-PLANE APPROACH TO THE EDGE-WEIGHTED MAXIMAL CLIQUE PROBLEM
    DIJKHUIZEN, G
    FAIGLE, U
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1993, 69 (01) : 121 - 130
  • [4] Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
    Fomeni, Franklin Djeumou
    Kaparis, Konstantinos
    Letchford, Adam N.
    [J]. MATHEMATICAL PROGRAMMING, 2015, 151 (02) : 639 - 658
  • [5] A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
    Fomeni, Franklin Djeumou
    Letchford, Adam N.
    [J]. INFORMS JOURNAL ON COMPUTING, 2014, 26 (01) : 173 - 182
  • [6] A semidefinite programming approach to the quadratic knapsack problem
    Helmberg, C
    Rendl, F
    Weismantel, R
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2000, 4 (02) : 197 - 215
  • [7] A Lagrangian relaxation approach to the edge-weighted clique problem
    Hunting, M
    Faigle, U
    Kern, W
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2001, 131 (01) : 119 - 131
  • [8] Hunting M., 1998, THESIS
  • [9] MIN-CUT CLUSTERING
    JOHNSON, EL
    MEHROTRA, A
    NEMHAUSER, GL
    [J]. MATHEMATICAL PROGRAMMING, 1993, 62 (01) : 133 - 151
  • [10] KUBY MJ, 1987, GEOGR ANAL, V19, P315
12