Speaker: Hendrik Bierlee
KU Leuven/OPTIMA

Title: Table Constraints for Integer Programming

Abstract:
Global constraints are a central concept in Constraint Programming (CP), which allows modellers to compactly express complex relations, and allows 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 Boolean decomposition, as well as an 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.

This talk presents work from a project authoured by:
Hendrik Bierlee (KU Leuven/OPTIMA)
Wout Piessens (KU Leuven)
Tias Guns (KU Leuven)
Peter Stuckey (Monash University/OPTIMA)

—
JOIN VIA ZOOM – MEETING ID: 873 1557 5255; PASSWORD: 778635

SEMINAR: WED 10 June 2026 16:00-17:00 AEST (Melbourne Time)/ 08:00 CEST