A Random-Key Optimizer for a Balanced Edge Partitioning Problem

We present a mixed-integer programming model and a random-key optimizer (RKO) for a balanced edge partitioning problem (BEP) on an undirected graph. In this problem, given a number of partitions into which we assign edges, the number of edges in each partition should be as similar as possible. The objective is to minimize the cost of the partitioning. We use 162 instances to illustrate that for small graphs and a small number of partitions, the mathematical model produces
an optimal solution. However, as the size of the graph increases and there are more partitions, the use of a heuristic is required. RKO is shown to be a good option for such large graphs, finding near-optimal solutions.