Solving a multicoloring problem with overlaps using integer programming | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.contributor.author | Méndez Díaz, Isabel | |
| dc.contributor.author | Zabala, Paula Lorena | |
| dc.date.issued | 2010-02 | |
| dc.description.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. | es |
| dc.description.fil | Fil: Méndez Díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Zabala, Paula Lorena. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | 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 | es |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.uri | http://hdl.handle.net/11336/16547 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 4 | es |
| dc.journal.pagination | 349-354 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 158 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2009.05.007 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0166218X09002650 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Graph Multicoloring | es |
| dc.subject | Integer Programming | es |
| dc.subject | Branch And Cut | es |
| dc.subject.classification | Otras Ciencias de la Computación e Información | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Solving a multicoloring problem with overlaps using integer programming | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.20314.pdf
- Tamaño:
- 365.01 KB
- Formato:
- Adobe Portable Document Format
- Descripción: