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-Diaz, I., Nasini, G., Severín, D.
Formato:	JOUR
Materias:	Branch & cut Equitable graph coloring Integer programming
Acceso en línea:	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	todo:paper_15710653_v37_nC_p159_MendezDiaz
record_format	dspace
spelling	todo:paper_15710653_v37_nC_p159_MendezDiaz2023-10-03T16:27:05Z Polyhedral results for the equitable coloring problem Méndez-Diaz, I. Nasini, G. Severín, D. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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-Diaz, I. Nasini, G. Severín, D. 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.
format	JOUR
author	Méndez-Diaz, I. Nasini, G. Severín, D.
author_facet	Méndez-Diaz, I. Nasini, G. Severín, D.
author_sort	Méndez-Diaz, I.
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
url	http://hdl.handle.net/20.500.12110/paper_15710653_v37_nC_p159_MendezDiaz
work_keys_str_mv	AT mendezdiazi polyhedralresultsfortheequitablecoloringproblem AT nasinig polyhedralresultsfortheequitablecoloringproblem AT severind polyhedralresultsfortheequitablecoloringproblem
_version_	1807323073852997632

Polyhedral results for the equitable coloring problem

Ejemplares similares