DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.47

Revisiting Integer Programming Encodings of Acyclicity

Authors: Masood Feyzbakhsh Rankooh and Matti Järvisalo

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

We study generic integer programming (IP) encodings of acyclicity in directed graphs as a key constraint in various real-world problem domains. We analyze both classical and more recently-proposed generic acyclicity encodings, including Miller-Tucker-Zemlin (MTZ), feedback vertex set (FVS), vertex elimination (VE), and cycle elimination (CE) based encodings in terms of their linear programming (LP) relaxation tightness. We also introduce hybrid encodings combining sought-after properties of the individual encodings. For the hybrids, we establish tightness guarantees for their LP relaxations that interpolate smoothly between the individual encodings. Our results show that VE and CE yield equally strong relaxations and strictly dominate MTZ and FVS, while the hybrid encoding schemes become increasingly tight as the elimination prefix grows. Mapping theory to practice, we empirically evaluate the encodings on both direct IP encodings of problem domains, where acyclicity is a key constraint. The results both validate our theoretical findings and yield promising runtime performance.

Cite as

Masood Feyzbakhsh Rankooh and Matti Järvisalo. Revisiting Integer Programming Encodings of Acyclicity. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 47:1-47:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rankooh_et_al:LIPIcs.CP.2026.47,
  author =	{Rankooh, Masood Feyzbakhsh and J\"{a}rvisalo, Matti},
  title =	{{Revisiting Integer Programming Encodings of Acyclicity}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{47:1--47:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.47},
  URN =		{urn:nbn:de:0030-drops-266806},
  doi =		{10.4230/LIPIcs.CP.2026.47},
  annote =	{Keywords: Operations research, integer programming encodings, acyclicity, tightness}
}

Search Results

Documents authored by Rankooh, Masood Feyzbakhsh

Revisiting Integer Programming Encodings of Acyclicity

Abstract

Cite as

Thanks for your feedback!

Could not send message