Strong ILP Formulations for the p-Regions Problem
2026-07-06 • Discrete Mathematics
Discrete MathematicsData Structures and Algorithms
AI summaryⓘ
The authors study how to divide a large map into smaller connected regions that are similar based on certain attributes, a problem known to be very hard to solve exactly. They introduce a new mathematical model called ER-S for this task, linking it to another known problem called k-partitioning. They also improve an existing model, adding a special rule to prevent invalid solutions. By combining these approaches, their new model ER-S-Tree is stronger and works better in practice, allowing them to solve regionalization problems for big countries in Europe that were too complex before.
regionalizationp-regions problemplanar subdivisionadjacency graphILP (Integer Linear Programming)k-partitioning problemsubtour elimination inequalityNP-hard problempolyhedral strength
Authors
Daniel Faber, Jan-Henrik Haunert, Petra Mutzel
Abstract
Regionalization is a fundamental task in spatial analysis that seeks to partition a larger area - such as a country - into smaller regions that are homogeneous with respect to a given attribute. A popular model for regionalization is the p-regions problem, in which regions are formed by grouping the areas of an input planar subdivision. Given the subdivision's adjacency graph G and pairwise dissimilarities between vertices, the goal is to partition G into a fixed number p of connected subgraphs, such as to minimize the sum of dissimilarities over all vertex pairs in the same subgraph. The problem is NP-hard and even small instances are difficult to solve to provable optimality. In this paper, we present the new ILP model ER-S for the p-regions problem, exploiting a connection between the p-regions objective and the k-partitioning problem. Furthermore, we strengthen the known ILP model Tree with a new type of subtour elimination inequality specific to the p-regions problem. Combining ER-S and the strengthened version of Tree yields the model ER-S-Tree, which dominates the state-of-the-art models in polyhedral strength. This theoretical advantage is reflected in its superior performance in our experimental evaluation. In particular, the new models ER-S and ER-S-Tree enable the solution of problem instances for major European countries that were previously intractable.