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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2020-10-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440621001313 |
| _version_ | 1818460665306677248 |
|---|---|
| author | Diego Recalde Ramiro Torres Polo Vaca |
| author_facet | Diego Recalde Ramiro Torres Polo Vaca |
| author_sort | Diego Recalde |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-12-14T23:33:51Z |
| format | Article |
| id | doaj.art-5d5107523e8947faa2d68e575fb9853f |
| institution | Directory Open Access Journal |
| issn | 2192-4406 |
| language | English |
| last_indexed | 2024-12-14T23:33:51Z |
| publishDate | 2020-10-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj.art-5d5107523e8947faa2d68e575fb9853f2022-12-21T22:43:40ZengElsevierEURO Journal on Computational Optimization2192-44062020-10-0183289308An exact approach for the multi-constraint graph partitioning problemDiego Recalde0Ramiro Torres1Polo Vaca2Department of Mathematics, Escuela Politécnica Nacional, Ladrón de Guevara E11-253, Quito, Ecuador.; Research Center on Mathematical Modelling (MODEMAT), Escuela Politécnica Nacional, Quito, Ecuador.Department of Mathematics, Escuela Politécnica Nacional, Ladrón de Guevara E11-253, Quito, Ecuador.Department of Mathematics, Escuela Politécnica Nacional, Ladrón de Guevara E11-253, Quito, Ecuador.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.http://www.sciencedirect.com/science/article/pii/S219244062100131390C1090C2790C5705C70 |
| spellingShingle | Diego Recalde Ramiro Torres Polo Vaca An exact approach for the multi-constraint graph partitioning problem EURO Journal on Computational Optimization 90C10 90C27 90C57 05C70 |
| title | 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_short | An exact approach for the multi-constraint graph partitioning problem |
| title_sort | exact approach for the multi constraint graph partitioning problem |
| topic | 90C10 90C27 90C57 05C70 |
| url | http://www.sciencedirect.com/science/article/pii/S2192440621001313 |
| work_keys_str_mv | AT diegorecalde anexactapproachforthemulticonstraintgraphpartitioningproblem AT ramirotorres anexactapproachforthemulticonstraintgraphpartitioningproblem AT polovaca anexactapproachforthemulticonstraintgraphpartitioningproblem AT diegorecalde exactapproachforthemulticonstraintgraphpartitioningproblem AT ramirotorres exactapproachforthemulticonstraintgraphpartitioningproblem AT polovaca exactapproachforthemulticonstraintgraphpartitioningproblem |