Optimal partitioning of n-tuples

Question

Motivation

Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into solving the problem but I'm still unsatisfied with my solution.

Problem formulation

You are given a list of unique sets $X_1,\dots,X_n$, each containing four integers. You are also given an integer $k$. The goal is to partition the sets into $k$ groups, so that every group has between $0.8n/k$ and $1.2n/k$ sets, in a way that minimizes the number of different integers in each group. Formally, the goal is to find a function $f:\{1,\dots,n\} \to \{1,\dots,k\}$ that minimizes

$$\Phi(f) = \sum_j \left|\bigcup_{i \in f^{-1}(j)} X_i\right|.$$

Example

If instead of sets of four integers we considered sets of two integers, we could give the following example: for the sets

{1, 2}, {2, 3}, {1, 3}, {3, 4}, {4, 5}, {3, 5}

the optimal partitioning for $k=2$ would be {1, 2}, {2, 3}, {1, 3} and {3, 4}, {4, 5}, {3, 5} with unique elements $|\{1, 2, 3\}|=3$, $|\{3, 4, 5\}|=3$ and $\Phi = 6$.

My attempts so far

So far I've attempted to solve this problem by modeling it as a graph partitioning problem and using KaHIP library to do the computation. I thought of two methods of how to model this problem as a graph.

1. Each set is a vertex, and we have an edge between two vertices if they share an integer. The number of shared integers determines the weight of the edge. The graph partitioning tool then directly yields some solution to our problem.
2. Each unique integer that occurs in any set is a vertex, and we put an edge between two integers if they are both contained in the same set. The number of such cases determines the weight of the edge. Having the integers partitioned like this we can assign each set a partition of some of its integers. Resulting partitions can be too large, but that can be resolved by applying the first approach to these now relatively small partitions.

The first model in my case turned out to be very space-consuming. I have approximately 2 millions of these sets and the first model produced over 74M edges. The second approach helps a great deal and yields results of similar quality.

The problem is that neither of these models is the exact model of my original problem. Notably, the number of cut edges will not correspond with the number of duplicated integers across partitions. Can you think of a better graph model or an altogether different approach to this problem that would yield better results?

Answer 1

You might start from an initial solution computed using one of your two models, and then apply local search: consider any movement of one set from a group to another, and apply it if it does not violate the group constraints and it improves $\Phi$.

Local search is a common approach in graph partitioning, thus it is probably already a part of what KaHIP is doing, but even if it is, you would now do it with the correct measure, $\Phi$, not its surrogate, so the outcome is likely to be improved.