Propagating Regular Counting Constraints
Authors: Nicolas Beldiceanu, Pierre Flener, Justin Pearson, Pascal Van Hentenryck
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluated their merits as follows. We generated random c DFAs of up to five states (it is very important to note that all 34 counter automata of the Global Constraint Catalogue (Beldiceanu et al. 2007) have at most five states, since counters are a very powerful device that allows a drastic reduction from the number of states needed by using a conventional DFA) using the random DFA generator (Almeida, Moreira, and Reis 2007) of FAdo (version 0.9.6) and doing a counter increase by 1 on each arc with a probability of 20%. For each random c DFA, we generated random instances, with random lengths (up to n = 10) of X = [x1, . . . , xn] and random initial domains of the counter variable N (one value, two values, and intervals of length 2 or 3) and the signature variables si (intervals of any length, and sets with holes). The results, upon many millions of random instances, are that our REGCOUNT propagator never propagates less but often more, to the point of detecting more failures, than the built-in AUTOMATON (Beldiceanu, Carlsson, and Petit 2004) of SICStus Prolog. Further, it is already up to 3 times faster than the latter, even though it is na ıvely implemented in Prolog, while the built-in works by decomposition into a conjunction of TABLE constraints (with tuples according to the transition function δ), which is very carefully implemented in C. There is thus strong reason to believe that our propagators will do better on any benchmark. Also, no counterexample to the domain consistency of REGCOUNTATMOST has been generated and no pruning by the propagators of actually supported values was observed, giving a sanity check while proving Theorems 1 and 2. Table 1 gives the cumulative runtimes (under Mac OS X 10.7.5 on a 2.8 GHz Intel Core 2 Duo with a 4 GB RAM), the numbers of detected failures, and (when both propagators succeed) the numbers of pruned values for random instances of some constraints, the four-state c DFA for the NUMBERWORD(N, X, toto ) constraint being unnecessary to reproduce here. |
| Researcher Affiliation | Academia | Nicolas Beldiceanu TASC team (CNRS/INRIA) Mines de Nantes 44307 Nantes, France Pierre Flener and Justin Pearson Department of Information Technology Uppsala University 751 05 Uppsala, Sweden Pascal Van Hentenryck Optimization Research Group, NICTA and Australian National University Canberra, Australia |
| Pseudocode | No | The paper describes inductive definitions and computational steps but does not present them in a clearly labeled pseudocode or algorithm block. |
| Open Source Code | Yes | The full source code is in (Beldiceanu et al. 2013). Available at http://arxiv.org/abs/1309.7145. |
| Open Datasets | No | The paper states: "We generated random c DFAs... For each random c DFA, we generated random instances, with random lengths (up to n = 10) of X = [x1, . . . , xn] and random initial domains of the counter variable N (one value, two values, and intervals of length 2 or 3) and the signature variables si (intervals of any length, and sets with holes)." This describes a data generation process rather than providing access to a publicly available, pre-existing dataset. |
| Dataset Splits | No | The paper describes generating random instances and evaluating them, but it does not specify training, validation, or test splits, or a cross-validation setup. |
| Hardware Specification | Yes | Table 1 gives the cumulative runtimes (under Mac OS X 10.7.5 on a 2.8 GHz Intel Core 2 Duo with a 4 GB RAM), the numbers of detected failures, and (when both propagators succeed) the numbers of pruned values for random instances of some constraints, the four-state c DFA for the NUMBERWORD(N, X, toto ) constraint being unnecessary to reproduce here. |
| Software Dependencies | Yes | We implemented in SICStus Prolog version 4.2.1 (Carlsson, Ottosson, and Carlson 1997) the described propagators for REGCOUNTATMOST, REGCOUNTATLEAST, and REGCOUNT. The FAdo tool is available at http://fado.dcc.fc.up.pt/. |
| Experiment Setup | Yes | We generated random c DFAs of up to five states... doing a counter increase by 1 on each arc with a probability of 20%. For each random c DFA, we generated random instances, with random lengths (up to n = 10) of X = [x1, . . . , xn] and random initial domains of the counter variable N (one value, two values, and intervals of length 2 or 3) and the signature variables si (intervals of any length, and sets with holes). |