An exact approach for the multi-constraint graph partitioning problem

Diego Recalde (), Ramiro Torres () and Polo Vaca ()
Additional contact information
Diego Recalde: Escuela Politécnica Nacional
Ramiro Torres: Escuela Politécnica Nacional
Polo Vaca: Escuela Politécnica Nacional

EURO Journal on Computational Optimization, 2020, vol. 8, issue 3, No 5, 289-308

Abstract: Abstract 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.

Keywords: Graph partitioning; Integer programming; Branch & Cut; 90C10; 90C27; 90C57; 05C70 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-020-00126-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:8:y:2020:i:3:d:10.1007_s13675-020-00126-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-020-00126-9

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().