Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420347 | Discrete Applied Mathematics | 2010 | 6 Pages |
Abstract
This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Isabel Méndez-Díaz, Paula Zabala,