Méndez-Díaz, I. - Zabala, P.

En:

Discrete Appl Math 2010;158(4):349-354

Fecha:

2010

Formato:

application/pdf

Tipo de documento:

info:eu-repo/semantics/article
info:ar-repo/semantics/artículo
info:eu-repo/semantics/publishedVersion

Descriptores:

Branch-and-Cut - Graph multicoloring - Integer programming - Branch-and-cut - Branch-and-cut algorithms - Graph multicoloring - Integer programming formulations - Multicoloring - Polytopes

Descripción:

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.

Identificador(es):

http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n4_p349_MendezDiaz

Derechos:

info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by/2.5/ar

Descargar texto: paper_0166218X_v158_n4_p349_MendezDiaz.oai

(tamaño kb)

Cita bibliográfica:

Méndez-Díaz, I. (2010). Solving a multicoloring problem with overlaps using integer programming (info:eu-repo/semantics/article). [consultado: ] Disponible en el Repositorio Digital Institucional de la Universidad de Buenos Aires: <http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&cl=CL1&d=paper_0166218X_v158_n4_p349_MendezDiaz_oai>