An exact approach for the multi-constraint graph partitioning problem
- PDF / 388,954 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 69 Downloads / 305 Views
An exact approach for the multi-constraint graph partitioning problem Diego Recalde1,2
· Ramiro Torres1
· Polo Vaca1
Received: 31 October 2019 / Accepted: 18 May 2020 © The Association of European Operational Research Societies and Springer-Verlag GmbH Berlin Heidelberg 2020
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 subproblem 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 Mathematics Subject Classification 90C10 · 90C27 · 90C57 · 05C70
B
Ramiro Torres [email protected] Diego Recalde [email protected] Polo Vaca [email protected]
1
Department of Mathematics, Escuela Politécnica Nacional, Ladrón de Guevara E11-253, Quito, Ecuador
2
Research Center on Mathematical Modelling (MODEMAT), Escuela Politécnica Nacional, Quito, Ecuador
123
D. Recalde et al.
1 Introduction The aim of partitioning arises when a set of objects characterized by attributes must be grouped into several clusters, such that some requirements must be satisfied in each group (cardinality, lower and upper bounds over quantified attributes, etc). One can think of a network where the objects correspond to nodes of the graph; attributes determine a set of weights for each node, and similarity or dissimilarity between nodes can be expressed with the inclusion of a cost function over the edges joining a pair of them. A partition of the set of nodes is a collection of non-empty subsets (called clusters), pairwise disjoint, such that their union is the original set. If each cluster of a partition satisfies constraints involving the attributes of the nodes and some objective function is optimized, then a multi-constraint graph partitioning problem arises. This problem appears as a sub-problem in the following real-world application: The National Statistics Bureau of Ecuador (INEC) carries out monthly polls to monitor the behavior of consumer prices for basic commodities, which are collected from a fixed set of stores known a priori and located around a city in Ecuador Gutierrez et al. (2019). Each store has to be visited once a month by a pollster, who registers prices of some commodities previously specified by INEC. After the information is collected at the store, each pollster moves on to the next scheduled store. The polls must be performed on a fixed number of days, and the available numb
Data Loading...
