Clausal Encodings of Smart Tables That Keep Full Pruning

A table constraint lists the allowed combinations of values for a group of variables. A smart table compresses that list. Each row, or smart tuple, can mark some variables as "anything goes" (a wildcard) and can state simple conditions such as $x \geq 3$ or $x < y$ in place of concrete values. Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints shows that ordinary tables can be turned into smart tables automatically. On those smart tables, a dedicated pruning routine runs one to two orders of magnitude faster than ordinary-table pruning. The catch is that this routine only lives inside constraint-programming engines. SAT solvers, which learn from their own conflicts, and integer-programming (MIP) solvers accept only primitive pieces: clauses or linear inequalities. Translating a constraint into such pieces is called decomposition. Done naively, it either re-expands the compressed rows back to exponential size or loses pruning power. In the second case the solver can no longer rule out values that the original constraint would have ruled out. This loss is the "pruning gap."

We propose a direct translation of smart tables into clauses. It does not lose pruning power for a large and checkable class of smart tables, and its size grows with the compressed table rather than the expanded one. The construction gives each smart tuple its own private copies of only the variables that tuple actually constrains. The tuple's conditions are written as binary clauses over those copies, and each copy is tied back to the original variable through a switch variable that says whether the tuple is in use. Wildcard variables get no copies at all, and this is where the compression survives the translation. Two facts carry the argument. First, when a tuple's conditions form a tree, ordinary pairwise consistency on the copies is as strong as full consistency for that tuple. Wang and Yap proved this tree property for decision-diagram encodings. Second, the clause-solver's basic inference step, unit propagation, performs exactly that pairwise reasoning on support-style clauses.

Core Claim

Fix a smart table $T$ over variables with domains of size at most $d$. Let $r_t$ be the number of variables that tuple $t$ does not wildcard. Suppose every tuple's internal condition graph is acyclic. This graph has one node per constrained variable and one edge per binary condition $x \,\mathrm{op}\, y$, with $\mathrm{op} \in \{=, \neq, <, \leq\}$. Under that assumption there is a clause encoding whose size is roughly

$$ \sum_{t \in T} \big( r_t \, d + e_t \, d^2 \big), $$

where $e_t$ is the number of binary conditions in tuple $t$. The $d^2$ factor drops to $d$ for order comparisons if the copies use an order encoding, meaning literals of the form "$x \leq a$." On this encoding, unit propagation removes exactly the values that the smart-table pruning routine of Le Charlier et al. removes. In constraint-programming terms, it enforces generalized arc consistency (GAC), which means every value left in a domain belongs to at least one satisfying assignment of the constraint.

If some tuples are cyclic, we cut each cycle by splitting the tuple on one variable. This costs a factor of $d$ per cut variable and restores the guarantee. The claim is new because it carries the compression of smart tables into a solver family that currently has no access to it, and it does so without the pruning gap.

How this differs from the closest work

Two papers motivate the gap, because they show that compressed tables pay off but only inside constraint-programming engines. Extending Simple Tabular Reduction with Short Supports compresses tables with wildcards and filters them with its SHORTSTR2 routine. Automatic Synthesis of Smart Table Constraints by Abstraction of Table Constraints adds relational conditions. Both keep the compressed table as a single block handled by one specialized routine and never decompose it.

Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees supplies the method. It decomposes a multi-valued decision diagram (MDD), a shared-path graph representing the allowed tuples, into a tree of binary constraints over hidden variables. It proves that pairwise consistency on that tree equals GAC. We reuse that tree argument, but we apply it per smart tuple and inside a disjunction over tuples, rather than across one global diagram. Starting from smart tables matters because it avoids first compiling to an MDD, which may be larger.

The theory papers constrain the design. Encoding Constraints as Binary Constraint Networks Satisfying BTP places smart tables below broken-triangle networks in a succinctness hierarchy and proves that such networks are limited to monotone reasoning. Our encoding stays within what that hierarchy allows. Smart tables admit polynomial pairwise-consistency encodings, so a polynomial clause encoding with complete propagation is not ruled out. The Complexity of Reasoning with Global Constraints shows that no such guarantee is possible for NP-hard constraints. We therefore restrict attention to smart tables, where checking whether a value has support is polynomial.

Finally, Decompositions of All Different, Global Cardinality and Related Constraints is the model for the kind of result we want. It decomposes a global constraint into primitives, proves which consistency level survives, and measures the effect in a pseudo-Boolean solver. That paper adds auxiliary variables to preserve pruning. We add auxiliaries only for non-wildcard positions.

Research Program

The construction has four parts. Each smart tuple $t$ gets a switch literal $s_t$. For each variable $x$ that $t$ constrains, the tuple also gets copy literals $x^t{=}a$, one for each value $a$ allowed by $t$'s unary conditions on $x$.

Channelling clauses tie the copies to the originals. They state that a copy value implies both the switch and the original value. They also state that the switch together with the original value implies the copy value, and that the switch implies at least one copy value.

Support clauses encode each binary condition on the copies. For a condition between $x$ and $y$, the clause says that $x^t{=}a$ implies the disjunction of the compatible $y^t{=}b$. For order conditions, chains of order literals replace these clauses.

Coverage clauses say that $x{=}a$ implies the disjunction of $x^t{=}a$ over the tuples that constrain $x$ and admit $a$. The value $x{=}a$ is free whenever some tuple wildcards $x$, and in that case the coverage clause is dropped. A final clause says that at least one switch is on.

The first deliverable is a proof that unit propagation on this encoding equals GAC whenever every tuple's condition graph is a forest. We will also give a small counterexample showing that the guarantee fails on a cyclic tuple. The second deliverable is the cycle-cutting step, with a size bound in terms of the cutset size. The third is a linear-inequality version of the same clauses for MIP solvers.

We will also measure how often acyclicity holds in practice. We take tables synthesized by the Le Charlier et al. procedure and record the distribution of cutset sizes. This is an honest unknown. If synthesized tuples are routinely cyclic, the size advantage shrinks, and the study reports that.

Baselines

The naive reference point expands the smart table back into an ordinary table. It then uses the standard switch-per-row clause encoding, which also preserves GAC but has one switch per explicit row. On lex-10-4, whose original table has 524,800 tuples according to Le Charlier et al., this baseline shows the cost that our encoding claims to avoid. We run it with the same SAT solver, the same time and memory limits, and default settings. Beating it means smaller encodings and faster solving on every instance where the smart table compresses.

The strongest decomposition competitor is the binary-constraint-tree route of Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees. We compile each table to an MDD, reduce it to a binary tree with their rules, and write that tree as support clauses. This route also preserves GAC, so the comparison isolates whether starting from smart tables buys size and speed. In a constraint-programming engine, that paper reports that its tree encoding was "the fastest algorithm on 71% of the table instances tested," up to 12x faster than the Compact Table algorithm, and up to 98x faster than the leading MDD propagator. We use their reduction rules unchanged and charge both routes their encoding time. We claim a win only if our clause count is smaller and our solve time is no worse on the majority of instances.

The strongest overall competitor is not a decomposition. It is the monolithic smart-table routine of Le Charlier et al. running inside a constraint-programming solver. That paper reports it is "one or two orders of magnitude" faster than the Compact Table algorithm and MDD propagators on lex-8-6 and distinctVectors-10-4. No absolute runtimes were found on Lacuna for those instances, so we re-run it ourselves. We do not expect to beat it on pure table puzzles. The target is mixed models, where clause learning and MIP relaxations matter, and there the SAT/MIP run with our encoding should outperform it.

Two ablations isolate the key ingredient. The first removes the per-tuple copies and guards each condition directly on the original variables with the switch. This version is smaller but loses GAC. The second gives every variable, wildcards included, a copy. It keeps GAC but discards the compression, which measures how much the wildcard saving contributes.

Why not just…?

Why not just keep the smart table as one block inside a constraint-programming solver? For pure table problems, this may well win, and we will report it plainly if it does. The case for decomposition rests on two facts. Monolithic routines cannot share internal state with other constraints, as argued in Decompositions of All Different, Global Cardinality and Related Constraints. They also cannot be fed to the SAT and hybrid solvers that broke Gecode's streak in The MiniZinc Challenge 2008-2013. The MiniZinc experiment below tests whether those facts translate into wins.

Why not just compile to an MDD and reuse the binary-tree encoding? This is the real threat, since it already preserves GAC and is fast. It falls short only if MDDs of synthesized smart tables are much larger than the smart tables themselves, especially when relational conditions link distant variables. The succinctness results in Encoding Constraints as Binary Constraint Networks Satisfying BTP make this plausible but do not establish it for these benchmarks. The head-to-head size comparison settles it. If MDD trees come out comparable in size, our contribution narrows to the acyclicity analysis and the MIP form.

Why not just guard each condition with the tuple's switch and skip the copies? That encoding is smaller, but unit propagation cannot chain reasoning through a condition whose switch is undecided. It therefore reopens the pruning gap. Decompositions of All Different, Global Cardinality and Related Constraints shows that a pruning gap of this kind can be decisive. On pigeonhole $n=11$, the weak binary decomposition took 29 seconds and nearly a million backtracks, against 0.1 seconds and 10 backtracks for the pruning-preserving one. The first ablation measures whether the same effect appears here.

Proposed Experiments

The table benchmarks are the instances from Le Charlier et al.: lex, element, maximum, atMost1, notAllEqual and distinctVectors, including lex-10-4, lex-8-6 and distinctVectors-10-4. We add the XCSP table instances, Pentominoes, Car Sequencing and Nurse Scheduling from Wang and Yap. To test the setting where decomposition should matter, we take MiniZinc Challenge models that contain table constraints alongside other constraints. We solve these with a CDCL SAT solver and a MIP solver, and compare against a constraint-programming solver using the monolithic routine.

The metrics are clause and variable counts, encoding time, solve time with a timeout, conflicts or backtracks, and memory. We also check the GAC claim directly. On random partial assignments, we compare the values removed by unit propagation against those removed by an exact GAC routine. The result must match on 100% of acyclic tables. Any mismatch falsifies the proof.

The proposal succeeds on two conditions. First, the GAC match holds and our encodings are smaller than both the expanded-table and MDD-tree encodings on most synthesized tables. Second, on mixed MiniZinc models, SAT or MIP solvers using our encoding beat the constraint-programming solver with the monolithic routine. The proposal fails if the MDD-tree route matches our size, or if acyclic tuples turn out to be rare.