2026-07-21T20:03:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26639 2026-07-13T14:00:36Z ddc:004 open_access

Table Constraints for Integer Programming Bierlee, Hendrik Piessens, Wout Guns, Tias Stuckey, Peter J. Table constraints integer programming cut generation modelling Global constraints are a central concept in Constraint Programming (CP), which allow modellers to compactly express complex relations, and which allow solvers to efficiently handle them. Table constraints have especially been well-studied as they can express arbitrary finite relations, and are extensively used in CP benchmarks. In this paper we study how to best deal with table constraints when using Integer Linear Programming (ILP) solvers. We study two paradigms: linear encodings, and a lazy cut generation approach. For the encoding we propose a novel MDD-based flow encoding. For the cut generation, in which lazy constraints are generated on-demand during branch-and-cut search, we investigate different ways of generating such integer and fractional cuts as well as how to strengthen them through shrinking and cut lifting. We experimentally compare the different approaches on CP competition instances with a wide variety of table constraints, showing clear benefits over the standard integer encoding. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hendrik Bierlee and Wout Piessens and Tias Guns and Peter J. Stuckey 2026 Is Part Of LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2026.6 urn:nbn:de:0030-drops-266397 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.6 eng https://creativecommons.org/licenses/by/4.0/legalcode