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
Lenguaje:Inglés
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
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_0166218X_v158_n4_p349_MendezDiaz
record_format dspace
spelling paperaa:paper_0166218X_v158_n4_p349_MendezDiaz2023-06-12T16:46:53Z Solving a multicoloring problem with overlaps using integer programming Discrete Appl Math 2010;158(4):349-354 Méndez-Díaz, I. Zabala, P. 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 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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)
language Inglés
orig_language_str_mv eng
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
work_keys_str_mv AT mendezdiazi solvingamulticoloringproblemwithoverlapsusingintegerprogramming
AT zabalap solvingamulticoloringproblemwithoverlapsusingintegerprogramming
_version_ 1769810284777570304

Ejemplares similares