{"ID":5937161,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T10:01:58.690261254Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.04886","arxiv_id":"2607.04886","title":"Strong ILP Formulations for the p-Regions Problem","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.","short_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 p...","url_abs":"https://arxiv.org/abs/2607.04886","url_pdf":"https://arxiv.org/pdf/2607.04886v1","authors":"[\"Daniel Faber\",\"Jan-Henrik Haunert\",\"Petra Mutzel\"]","published":"2026-07-06T10:11:22Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}