An exact approach for the multi-constraint graph partitioning problem

In this work, a multi-constraint graph partitioning problem is introduced. The input is an undirected graph with costs on the edges and multiple weights on the nodes. The problem calls for a partition of the node set into a fixed number of clusters, such that each cluster satisfies a collection of n...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Diego Recalde, Ramiro Torres, Polo Vaca
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2020
Materias:	90C10 90C27 90C57 05C70 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/5d5107523e8947faa2d68e575fb9853f
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:5d5107523e8947faa2d68e575fb9853f
record_format	dspace
spelling	oai:doaj.org-article:5d5107523e8947faa2d68e575fb9853f2021-12-03T04:01:15ZAn exact approach for the multi-constraint graph partitioning problem2192-440610.1007/s13675-020-00126-9https://doaj.org/article/5d5107523e8947faa2d68e575fb9853f2020-10-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621001313https://doaj.org/toc/2192-4406In this work, a multi-constraint graph partitioning problem is introduced. The input is an undirected graph with costs on the edges and multiple weights on the nodes. The problem calls for a partition of the node set into a fixed number of clusters, such that each cluster satisfies a collection of node weight constraints, and the total cost of the edges whose end nodes are in the same cluster is minimized. It arises as a sub-problem of an integrated vehicle and pollster problem from a real-world application. Two integer programming formulations are provided, and several families of valid inequalities associated with the respective polyhedra are proved. An exact algorithm based on Branch & Bound and cutting planes is proposed, and it is tested on real-world instances.Diego RecaldeRamiro TorresPolo VacaElsevierarticle90C1090C2790C5705C70Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 8, Iss 3, Pp 289-308 (2020)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C10 90C27 90C57 05C70 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C10 90C27 90C57 05C70 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Diego Recalde Ramiro Torres Polo Vaca An exact approach for the multi-constraint graph partitioning problem
description	In this work, a multi-constraint graph partitioning problem is introduced. The input is an undirected graph with costs on the edges and multiple weights on the nodes. The problem calls for a partition of the node set into a fixed number of clusters, such that each cluster satisfies a collection of node weight constraints, and the total cost of the edges whose end nodes are in the same cluster is minimized. It arises as a sub-problem of an integrated vehicle and pollster problem from a real-world application. Two integer programming formulations are provided, and several families of valid inequalities associated with the respective polyhedra are proved. An exact algorithm based on Branch & Bound and cutting planes is proposed, and it is tested on real-world instances.
format	article
author	Diego Recalde Ramiro Torres Polo Vaca
author_facet	Diego Recalde Ramiro Torres Polo Vaca
author_sort	Diego Recalde
title	An exact approach for the multi-constraint graph partitioning problem
title_short	An exact approach for the multi-constraint graph partitioning problem
title_full	An exact approach for the multi-constraint graph partitioning problem
title_fullStr	An exact approach for the multi-constraint graph partitioning problem
title_full_unstemmed	An exact approach for the multi-constraint graph partitioning problem
title_sort	exact approach for the multi-constraint graph partitioning problem
publisher	Elsevier
publishDate	2020
url	https://doaj.org/article/5d5107523e8947faa2d68e575fb9853f
work_keys_str_mv	AT diegorecalde anexactapproachforthemulticonstraintgraphpartitioningproblem AT ramirotorres anexactapproachforthemulticonstraintgraphpartitioningproblem AT polovaca anexactapproachforthemulticonstraintgraphpartitioningproblem AT diegorecalde exactapproachforthemulticonstraintgraphpartitioningproblem AT ramirotorres exactapproachforthemulticonstraintgraphpartitioningproblem AT polovaca exactapproachforthemulticonstraintgraphpartitioningproblem
_version_	1718373931612635136

An exact approach for the multi-constraint graph partitioning problem

Ejemplares similares