An unconstrained quadratic binary programming approach to the vertex coloring problem

被引:37
作者
Kochenberger, GA
Glover, F
Alidaee, B
Rego, C
机构
[1] Univ Colorado, Sch Business, Denver, CO 80217 USA
[2] Univ Colorado, Leeds Sch Business, Boulder, CO 80309 USA
[3] Univ Mississippi, Hearin Ctr Enterprise Sci, University, MS 38677 USA
关键词
graph coloring; combinatorial optimization; tabu search;
D O I
10.1007/s10479-005-3449-7
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.
引用
收藏
页码:229 / 241
页数:13
相关论文
共 50 条
  • [1] 0-1 QUADRATIC-PROGRAMMING APPROACH FOR OPTIMUM SOLUTIONS OF 2 SCHEDULING PROBLEMS
    ALIDAEE, B
    KOCHENBERGER, GA
    AHMADIAN, A
    [J]. INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 1994, 25 (02) : 401 - 408
  • [2] Simulated annealing for the unconstrained quadratic pseudo-Boolean function
    Alkhamis, TM
    Hasan, M
    Ahmed, MA
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 108 (03) : 641 - 652
  • [3] Amini M. M., 1999, NEW METHODS OPTIMIZA, P317
  • [4] [Anonymous], 1997, Tabu Search
  • [5] AN APPLICATION OF COMBINATORIAL OPTIMIZATION TO STATISTICAL PHYSICS AND CIRCUIT LAYOUT DESIGN
    BARAHONA, F
    GROTSCHEL, M
    JUNGER, M
    REINELT, G
    [J]. OPERATIONS RESEARCH, 1988, 36 (03) : 493 - 513
  • [6] BEASLEY JE, 1999, HEURISTIC ALGORITHMS
  • [7] MINIMIZATION OF A QUADRATIC PSEUDO-BOOLEAN FUNCTION
    BILLIONNET, A
    SUTTER, A
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 78 (01) : 106 - 115
  • [8] Boros E, 2002, DISCRETE APPL MATH, V123, P1
  • [9] Boros E., 1989, Annals of Operations Research, V21, P109, DOI 10.1007/BF02022095
  • [10] BORROS E, 3989 RUTCOR RRR RES