Auto-tabling for subproblem presolving in MiniZinc

A well-known and powerful constraint model reformulation is to compute the solutions to a model part, say a custom constraint predicate, and tabulate them within an extensional constraint that replaces that model part. Despite the possibility of achieving higher solving performance, this tabling reformulation is often not tried, because it is tedious to perform; further, if successful, it obfuscates the original model. In order to encourage modellers to try tabling, we extend the MiniZinc toolchain to perform the automatic tabling of suitably annotated predicate definitions, without requiring any changes to solvers, thereby eliminating both the tedium and the obfuscation. Our experiments show that automated tabling yields the same tables as manual tabling, and that tabling is beneficial for solvers of several solving technologies.

• Publication year

  2017

• Venue

  Constraints

• Publication date

  2017-10-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1007/s10601-017-9270-5
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Decision diagrams for optimization

  2018cited by this paper
• Scheduling double round-robin tournaments with divisional play using constraint programming

  2017cited by this paper
• Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets

  2016cited by this paper
• Sub-Problem Pre-Solving in MiniZinc

  2016cited by this paper
• Improved Linearization of Constraint Programming Models

  2016cited by this paper
• MiniSearch: A Solver-Independent Meta-Search Language for MiniZinc

  2015cited by this paper
• A constraint-based local search backend for MiniZinc

  2015cited by this paper
• Multi-Pass High-Level Presolving

  2015cited by this paper
• Automated Auxiliary Variable Elimination Through On-the-Fly Propagator Generation

  2015cited by this paper
• Generating custom propagators for arbitrary constraints

  2014cited by this paper
• An Integrated Constraint Programming Approach to Scheduling Sports Leagues with Divisional and Round-Robin Tournaments

  2014cited by this paper
• Constructing schedules for sports leagues with divisional and round-robin tournaments

  2014cited by this paper
• Model Expansion in the Presence of Function Symbols Using Constraint Programming

  2013influential reference
• Improving combinatorial optimization

  2011influential reference
• A System for Solving Constraint Satisfaction Problems with SMT

  2010influential reference
• Maintaining Generalized Arc Consistency on Ad Hoc r-Ary Constraints

  2008cited by this paper
• Proceedings of ModRef'08, the Seventh International Workshop on Constraint Modelling and Reformulation

  2008cited by this paper
• MiniZinc: Towards a Standard CP Modelling Language

  2007cited by this paper
• Search in the patience game ‘Black Hole’

  2007cited by this paper
• Effective Preprocessing in SAT Through Variable and Clause Elimination

  2005cited by this paper
• A Regular Language Membership Constraint for Finite Sequences of Variables

  2004cited by this paper
• Automatic generation of rule-based constraint solvers over finite domains

  2004cited by this paper
• Enforcing Arc Consistency on Global Constraints by Solving Subproblems on the Fly

  1999cited by this paper
• An Open-Ended Finite Domain Constraint Solver

  1997cited by this paper
• Domain Independent Propagation

  1992cited by this paper
• The Penguin Book of Patience

  1979cited by this paper

• Parameterised Treewidth for Constraint Modelling Languages

  2024cites this paper
• Learning When to Use Automatic Tabulation in Constraint Model Reformulation

  2023cites this paper
• The Expressive Power of Ad-Hoc Constraints for Modelling CSPs

  2023cites this paper
• Exact and metaheuristic methods for a real-world examination timetabling problem

  2023cites this paper
• Tables segmentées : un outil de modélisation efficace pour le raisonnement par contraintes

  2021cites this paper
• Constrained Machine Learning: The Bagel Framework

  2021cites this paper
• Declarative Programming and Knowledge Management: Conference on Declarative Programming, DECLARE 2019, Unifying INAP, WLP, and WFLP, Cottbus, Germany, September 9–12, 2019, Revised Selected Papers

  2020cites this paper
• Reformulations of Constraint Satisfaction Problems: A Survey

  2020cites this paper
• Segmented Tables: An Efficient Modeling Tool for Constraint Reasoning

  2020cites this paper
• The Regularization of Small Sub-Constraint Satisfaction Problems

  2019cites this paper
• Automatic Predicate Encapsulation of Potentially Profitably Presolvable Submodels in MiniZinc

  2018influential citation
• Automatic Discovery and Exploitation of Promising Subproblems for Tabulation

  2018influential citation
• Proceedings of the 2018 XCSP3 Competition

  2018influential citation
• Compiling CP subproblems to MDDs and d-DNNFs

  2018influential citation
• Discrete optimization over graph problems

  2018cites this paper
• Efficient Reification of Table Constraints

  2017cites this paper