Skip to Main content Skip to Navigation
Journal articles

The K ‐partitioning problem: Formulations and branch‐and‐cut

Abstract : The K-partitioning problem consists in partitioning the nodes of a complete graph G = (V, E) with weights on the edges in exactly K clusters such that the sum of the weights of the edges inside the clusters is minimized. For this problem, we propose two node-cluster formulations adapted from the literature on similar problems as well as two edge-representative formulations. We introduced the first edge-representative formulation in a previous work [4] while the second is obtained by adding an additional set of edge variables. We compare the structure of the polytopes of the two edge-representative formulations and identify a new family of facet-defining inequalities. The quality of the linear relaxation and the resolution times of the four formulations are compared on various data sets. We provide bounds on the relaxation values of the node-cluster formulations which may account for their low performances. Finally, we propose a branch-and-cut strategy, based on the edge-representative formulations, which performs even better.
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02932003
Contributor : Zacharie Ales <>
Submitted on : Monday, September 7, 2020 - 2:13:41 PM
Last modification on : Wednesday, September 16, 2020 - 3:20:37 AM

File

ales2020kpartitioning.pdf
Files produced by the author(s)

Identifiers

Citation

Zacharie Alès, Arnaud Knippel. The K ‐partitioning problem: Formulations and branch‐and‐cut. Networks, Wiley, 2020, 76 (3), pp.323-349. ⟨10.1002/net.21944⟩. ⟨hal-02932003⟩

Share

Metrics

Record views

15

Files downloads

13