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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Méndez Díaz, Isabel, Zabala, Paula
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: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:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0166218X_v158_n4_p349_MendezDiaz
record_format dspace
spelling paper:paper_0166218X_v158_n4_p349_MendezDiaz2025-07-30T17:54:21Z 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_ 1840321617675157504

Ejemplares similares