| Autor: |
Diego Recalde, Ramiro Torres, Polo Vaca |
| Jazyk: |
angličtina |
| Rok vydání: |
2020 |
| Předmět: |
|
| Zdroj: |
EURO Journal on Computational Optimization, Vol 8, Iss 3, Pp 289-308 (2020) |
| Druh dokumentu: |
article |
| ISSN: |
2192-4406 |
| DOI: |
10.1007/s13675-020-00126-9 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
Full text from SpringerLink