DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.13

Strong ILP Formulations for the p-Regions Problem

Authors: Daniel Faber, Jan-Henrik Haunert, and Petra Mutzel

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

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.

Cite as

Daniel Faber, Jan-Henrik Haunert, and Petra Mutzel. Strong ILP Formulations for the p-Regions Problem. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{faber_et_al:LIPIcs.ESA.2026.13,
  author =	{Faber, Daniel and Haunert, Jan-Henrik and Mutzel, Petra},
  title =	{{Strong ILP Formulations for the p-Regions Problem}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.13},
  URN =		{urn:nbn:de:0030-drops-271498},
  doi =		{10.4230/LIPIcs.ESA.2026.13},
  annote =	{Keywords: p-regions problem, connected graph partitioning, area aggregation, integer linear programming, branch-and-cut}
}

Document

DOI: 10.4230/LIPIcs.SAT.2024.12

SAT Encoding of Partial Ordering Models for Graph Coloring Problems

Authors: Daniel Faber, Adalat Jabrayilov, and Petra Mutzel

Published in: LIPIcs, Volume 305, 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)

Abstract

In this paper, we revisit SAT encodings of the partial-ordering based ILP model for the graph coloring problem (GCP) and suggest a generalization for the bandwidth coloring problem (BCP). The GCP asks for the minimum number of colors that can be assigned to the vertices of a given graph such that each two adjacent vertices get different colors. The BCP is a generalization, where each edge has a weight that enforces a minimal "distance" between the assigned colors, and the goal is to minimize the "largest" color used. For the widely studied GCP, we experimentally compare the partial-ordering based SAT encoding to the state-of-the-art approaches on the DIMACS benchmark set. Our evaluation confirms that this SAT encoding is effective for sparse graphs and even outperforms the state-of-the-art on some DIMACS instances. For the BCP, our theoretical analysis shows that the partial-ordering based SAT and ILP formulations have an asymptotically smaller size than that of the classical assignment-based model. Our practical evaluation confirms not only a dominance compared to the assignment-based encodings but also to the state-of-the-art approaches on a set of benchmark instances. Up to our knowledge, we have solved several open instances of the BCP from the literature for the first time.

Cite as

Daniel Faber, Adalat Jabrayilov, and Petra Mutzel. SAT Encoding of Partial Ordering Models for Graph Coloring Problems. In 27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 305, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{faber_et_al:LIPIcs.SAT.2024.12,
  author =	{Faber, Daniel and Jabrayilov, Adalat and Mutzel, Petra},
  title =	{{SAT Encoding of Partial Ordering Models for Graph Coloring Problems}},
  booktitle =	{27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-334-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{305},
  editor =	{Chakraborty, Supratik and Jiang, Jie-Hong Roland},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2024.12},
  URN =		{urn:nbn:de:0030-drops-205340},
  doi =		{10.4230/LIPIcs.SAT.2024.12},
  annote =	{Keywords: Graph coloring, bandwidth coloring, SAT encodings, ILP formulations}
}

Search Results

Documents authored by Faber, Daniel

Strong ILP Formulations for the p-Regions Problem

Abstract

Cite as

SAT Encoding of Partial Ordering Models for Graph Coloring Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message