Article ID: | iaor20061016 |
Country: | Netherlands |
Volume: | 139 |
Issue: | 1 |
Start Page Number: | 229 |
End Page Number: | 241 |
Publication Date: | Oct 2005 |
Journal: | Annals of Operations Research |
Authors: | Glover Fred, Kochenberger Gary A., Alidaee Bahram, Rego Cesar |
Keywords: | graphs, heuristics |
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.