info:eu-repo/semantics/article
Solving a multicoloring problem with overlaps using integer programming
Fecha
2010-02Registro en:
Méndez Díaz, Isabel; Zabala, Paula Lorena; Solving a multicoloring problem with overlaps using integer programming; Elsevier Science; Discrete Applied Mathematics; 158; 4; 2-2010; 349-354
0166-218X
Autor
Méndez Díaz, Isabel
Zabala, Paula Lorena
Resumen
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.