Extending Simple Tabular Reduction with Short Supports

Christopher Jefferson, Peter NightingaleIJCAI 2013

Introduction

In the field of Constraint Programming (CP), solvers tackle complex combinatorial problems—ranging from Sudoku and scheduling to hardware verification—by pruning the search space using "propagators." A common approach for general-purpose propagators is to use tables that explicitly list every valid combination of variable assignments, known as tuples. However, as problem complexity grows, these tables can expand astronomically, often exceeding available memory.

To address this, researchers have developed SHORTSTR2, an algorithm that leverages the concept of "short supports." A short support is a partial assignment of variables that satisfies a constraint regardless of the values assigned to the remaining variables. By focusing on these minimal subsets, SHORTSTR2 achieves significant compression and computational efficiency.

The SHORTSTR2 Framework

SHORTSTR2 builds upon the widely used "Simple Tabular Reduction" (STR2+) framework. It introduces two primary innovations:

1. Greedy Compression

Finding the absolute minimum set of short supports is an NP-complete problem. To make this practical, the authors developed Greedy-Compress. This heuristic takes a standard table of full-length tuples and iteratively collapses them into shorter versions by identifying variables that do not affect the constraint's satisfaction, replacing them with a wildcard symbol (*).

2. Efficient Propagation

The core SHORTSTR2 propagator maintains a set of "active" short supports during the search process. It utilizes two complementary data structures:

  • Long Form: An array representation including wildcards that allows for $O(1)$ value lookups.
  • Short Form: A compact list of variable-value pairs that enables the algorithm to iterate only through the variables essential to a specific support.

This dual-structure approach allows the solver to skip redundant checks on wildcard variables, drastically reducing the computational overhead during backtracking searches.

Experimental Evaluation

The algorithm was tested against several challenging benchmarks, including Quasigroup Existence (QG3), Rectangle Packing, and various "Oscillating Life" variants based on Conway’s Game of Life. It was also evaluated on standardized instances from the CSP Solver Competition.

Key Performance Results

The experiments demonstrated that SHORTSTR2 is particularly effective for constraints amenable to compression. In the "Quadlife" variant of the Game of Life, standard STR2+ failed due to memory limitations (exceeding 4GB), whereas SHORTSTR2 ran successfully.

Table 5: Performance comparison (nodes/sec) on Game of Life variants, highlighting SHORTSTR2's efficiency over HAGGISGAC.

In terms of raw speed, SHORTSTR2 often outperformed HAGGISGAC, a more complex state-of-the-art algorithm. For instance, on the "Vector Not-Equal" problem, SHORTSTR2 showed a performance advantage of up to a factor of two in several parameter configurations.

Table 4: Performance metrics for Vector Not-Equal instances across varying parameters p and a.

Insights and Future Work

The primary strength of SHORTSTR2 lies in its simplicity and "drop-in" compatibility with existing STR2+ implementations. While its performance gains are minimal on purely random, incompressible constraints, it offers exponential compression for many real-world structured constraints.

Future research aims to explore even more expressive grouping methods, such as "c-tuples" or tuple sequences, and to integrate SHORTSTR2 into a broader range of production-grade constraint solvers.

Summary updated

BibTeX
@inproceedings{jefferson2013extending,
  author = {Christopher Jefferson and Peter Nightingale},
  title = {{Extending Simple Tabular Reduction with Short Supports}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2013},
}
Figure