Solving a multicoloring problem with overlaps using integer programming

Mostrar todas las versiones(3)

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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Méndez-Díaz, I., Zabala, P.
Formato: Artículo publishedVersion
Publicado: 2010
Materias:
Branch-and-Cut
Graph multicoloring
Integer programming
Branch-and-cut
Branch-and-cut algorithms
Integer programming formulations
Multicoloring
Polytopes
Random instance
Valid inequality
Dynamic programming
Heuristic methods
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v158_n4_p349_MendezDiaz_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-paper_0166218X_v158_n4_p349_MendezDiaz_oai
record_format dspace
spelling I28-R145-paper_0166218X_v158_n4_p349_MendezDiaz_oai2024-08-16 Méndez-Díaz, I. Zabala, P. 2010 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Discrete Appl Math 2010;158(4):349-354 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 Solving a multicoloring problem with overlaps using integer programming info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v158_n4_p349_MendezDiaz_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (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, I.
Zabala, P.
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.
format Artículo
Artículo
publishedVersion
author Méndez-Díaz, I.
Zabala, P.
author_facet Méndez-Díaz, I.
Zabala, P.
author_sort Méndez-Díaz, I.
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 http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz
https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0166218X_v158_n4_p349_MendezDiaz_oai
work_keys_str_mv AT mendezdiazi solvingamulticoloringproblemwithoverlapsusingintegerprogramming
AT zabalap solvingamulticoloringproblemwithoverlapsusingintegerprogramming
_version_ 1809356901898518528

Ejemplares similares