Polyhedral results for the equitable coloring problem

In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effec...

Descripción completa

Detalles Bibliográficos
Autores principales:	Méndez Díaz, Isabel, Severin, Daniel E.
Publicado:	2011
Materias:	Branch & cut Equitable graph coloring Integer programming
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p159_MendezDiaz http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p159_MendezDiaz
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_15710653_v37_nC_p159_MendezDiaz
record_format	dspace
spelling	paper:paper_15710653_v37_nC_p159_MendezDiaz2023-06-08T16:24:26Z Polyhedral results for the equitable coloring problem Méndez Díaz, Isabel Severin, Daniel E. Branch & cut Equitable graph coloring Integer programming In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm. © 2011 Elsevier B.V. Fil:Méndez-Diaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Severín, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p159_MendezDiaz http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p159_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 & cut Equitable graph coloring Integer programming
spellingShingle	Branch & cut Equitable graph coloring Integer programming Méndez Díaz, Isabel Severin, Daniel E. Polyhedral results for the equitable coloring problem
topic_facet	Branch & cut Equitable graph coloring Integer programming
description	In this work we study the polytope associated with a 0/1 integer programming formulation for the Equitable Coloring Problem. We find several families of valid inequalities and derive sufficient conditions in order to be facet-defining inequalities. We also present computational evidence of the effectiveness of including these inequalities as cuts in a Branch & Cut algorithm. © 2011 Elsevier B.V.
author	Méndez Díaz, Isabel Severin, Daniel E.
author_facet	Méndez Díaz, Isabel Severin, Daniel E.
author_sort	Méndez Díaz, Isabel
title	Polyhedral results for the equitable coloring problem
title_short	Polyhedral results for the equitable coloring problem
title_full	Polyhedral results for the equitable coloring problem
title_fullStr	Polyhedral results for the equitable coloring problem
title_full_unstemmed	Polyhedral results for the equitable coloring problem
title_sort	polyhedral results for the equitable coloring problem
publishDate	2011
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v37_nC_p159_MendezDiaz http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p159_MendezDiaz
work_keys_str_mv	AT mendezdiazisabel polyhedralresultsfortheequitablecoloringproblem AT severindaniele polyhedralresultsfortheequitablecoloringproblem
_version_	1768542381905281024

Polyhedral results for the equitable coloring problem

Ejemplares similares