Solving a multicoloring problem with overlaps using integer programming
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...
Guardado en:
Autores principales: | , |
---|---|
Publicado: |
2010
|
Materias: | |
Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v158_n4_p349_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz |
Aporte de: |
id |
paper:paper_0166218X_v158_n4_p349_MendezDiaz |
---|---|
record_format |
dspace |
spelling |
paper:paper_0166218X_v158_n4_p349_MendezDiaz2023-06-08T15:15:29Z Solving a multicoloring problem with overlaps using integer programming Méndez Díaz, Isabel Zabala, Paula Branch-and-Cut Graph multicoloring Integer programming Branch-and-cut Branch-and-cut algorithms Graph multicoloring Integer programming formulations Multicoloring Polytopes Random instance Valid inequality Dynamic programming Heuristic methods Integer programming 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. © 2009 Elsevier B.V. All rights reserved. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Zabala, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2010 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v158_n4_p349_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz |
institution |
Universidad de Buenos Aires |
institution_str |
I-28 |
repository_str |
R-134 |
collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
topic |
Branch-and-Cut Graph multicoloring Integer programming Branch-and-cut Branch-and-cut algorithms Graph multicoloring Integer programming formulations Multicoloring Polytopes Random instance Valid inequality Dynamic programming Heuristic methods Integer programming |
spellingShingle |
Branch-and-Cut Graph multicoloring Integer programming Branch-and-cut Branch-and-cut algorithms Graph multicoloring Integer programming formulations Multicoloring Polytopes Random instance Valid inequality Dynamic programming Heuristic methods Integer programming Méndez Díaz, Isabel Zabala, Paula Solving a multicoloring problem with overlaps using integer programming |
topic_facet |
Branch-and-Cut Graph multicoloring Integer programming Branch-and-cut Branch-and-cut algorithms Graph multicoloring Integer programming formulations Multicoloring Polytopes Random instance Valid inequality Dynamic programming Heuristic methods Integer programming |
description |
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. © 2009 Elsevier B.V. All rights reserved. |
author |
Méndez Díaz, Isabel Zabala, Paula |
author_facet |
Méndez Díaz, Isabel Zabala, Paula |
author_sort |
Méndez Díaz, Isabel |
title |
Solving a multicoloring problem with overlaps using integer programming |
title_short |
Solving a multicoloring problem with overlaps using integer programming |
title_full |
Solving a multicoloring problem with overlaps using integer programming |
title_fullStr |
Solving a multicoloring problem with overlaps using integer programming |
title_full_unstemmed |
Solving a multicoloring problem with overlaps using integer programming |
title_sort |
solving a multicoloring problem with overlaps using integer programming |
publishDate |
2010 |
url |
https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v158_n4_p349_MendezDiaz http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz |
work_keys_str_mv |
AT mendezdiazisabel solvingamulticoloringproblemwithoverlapsusingintegerprogramming AT zabalapaula solvingamulticoloringproblemwithoverlapsusingintegerprogramming |
_version_ |
1768546393860866048 |