# ILP-based Local Search for Graph Partitioning

arXiv: https://arxiv.org/abs/1802.07144 · HTML: https://mlsanity.com/paper/1802.07144/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [More Recent Advances in (Hyper)Graph Partitioning](https://mlsanity.com/paper/2205.13202/) (2022)
- [K-SpecPart: Supervised embedding algorithms and cut overlay for improved hypergraph partitioning](https://mlsanity.com/paper/2305.06167/) (2023)

## Abstract (arXiv)

Computing high-quality graph partitions is a challenging problem with numerous applications. In this paper, we present a novel meta-heuristic for the balanced graph partitioning problem. Our approach is based on integer linear programs that solve the partitioning problem to optimality. However, since those programs typically do not scale to large inputs, we adapt them to heuristically improve a given partition. We do so by defining a much smaller model that allows us to use symmetry breaking and other techniques that make the approach scalable. For example, in Walshaw's well-known benchmark tables we are able to improve roughly half of all entries when the number of blocks is high.