Pith. sign in

REVIEW 4 major objections 4 minor 22 references

The Regularization of Small Sub-Constraint Satisfaction Problems

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Substituting a small solved sub-CSP with a single regular membership constraint preserves the solution set and speeds up constraint search in benchmarks.

desk verdict Correct DFA construction, honest about its own limitations, but the empirical speedup claim is not established by the reported evaluation. read the letter →

arxiv 1908.05907 v1 pith:QPKOLZ32 submitted 2019-08-16 cs.AI

Sven Löffler , Ke Liu , Petra Hofstedt This is my paper · ORCID
classification cs.AI
keywords constraintsatisfactionproblemsregularmembershipdeterministicfiniteautomatonsub-CSPsubstitutionpropagationpreprocessingtabulationSolitaireBattleships
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Constraint satisfaction problems can be modelled in more than one way, and the chosen model decides how fast a solver finds answers. This paper proposes a preprocessing transformation: solve a small sub-CSP completely, collect all of its solution tuples, and encode that set as a deterministic finite automaton $M$; then replace the sub-CSP's constraints by the single regular membership constraint $\mathrm{regular}(X', M)$. Because the automaton accepts exactly the tuples that satisfy the sub-CSP, the original problem's solution set is unchanged while the replacement constraint can propagate more strongly and fail earlier in search. In the Black Hole case study the regularized models found a first solution on average 82--84% faster than the original model and solved 47 of 50 instances within ten minutes instead of 7; in Solitaire Battleships plain regularization was slower, but a hybrid of regular and table constraints gave the best average improvement at 60.8%. Because the transformation happens before search, it can be combined with redundant modeling and parallel search techniques.

What carries the argument

The prefix-set DFA construction: for each position $i$, the set $T_i$ contains every length-$i$ prefix of a solution, and this set of prefixes becomes the state set of the automaton together with a start state and one accepting state for full solutions. This mechanism carries the argument because the automaton accepts exactly the finite language of solution tuples, and it underlies the regular membership constraint—the constraint that a tuple of values must be a word accepted by the automaton. The regular constraint's propagation algorithm filters each variable's domain to values that can still belong to an accepted word, which is what lets the solver prune more and fail earlier than it would with the original constraints.

What would settle it

Run the transformation on a benchmark suite and measure transformation time separately from search time: if any instance has transformation plus search slower than the original model, the claimed speedup fails, and the plain Regular Battleships results (average 11.6% slower) already provide such a case. Separately, enumerate all tuples accepted by the constructed DFA and compare them with the enumerated solutions of the sub-CSP; any mismatch would falsify the solution-set preservation claim.

Watch

Extended reading notes

Core claim

The central discovery is that any finite set of solution tuples of a sub-CSP can be encoded exactly as the language of a DFA built directly from the tuples' prefixes. For solutions $s_1,\dots,s_k$ over variables $x_1,\dots,x_n$, the construction forms $T_i$, the set of all length-$i$ prefixes of solutions, and makes each prefix a state; the start state stands for the empty prefix, and a transition consumes one domain value whenever the resulting longer prefix is also present. The only accepting state represents the complete solutions. The resulting DFA accepts a word exactly when that word is one of the enumerated solution tuples, so replacing the constraints of the sub-CSP by $\mathrm{regular}(X', M)$ preserves the solution set of the original CSP. The paper's experimental claim is that this replacement can also make search faster: in Black Hole the regularized configurations improved average first-solution time by 82.054% to 84.165%, and in Solitaire Battleships the strongest configuration combined regularized constraints with table constraints and improved average time by 60.763%.

Load-bearing premise

The method only pays off when a sub-CSP small enough to enumerate quickly can be found automatically; the paper uses a heuristic designed for table constraints and explicitly leaves automatic detection to future work, so when no such sub-CSP exists the preprocessing cost dominates and search slows down, as happened with plain Regular on Solitaire Battleships.

Editorial extensions

If this is right

  • Any finite sub-CSP can be collapsed into a single regular constraint without changing the solution set of the whole CSP, making the transformation a sound preprocessing step.
  • Regularized models can reduce search effort: in the Black Hole benchmark, first-solution times improved by roughly 82--84% on average and 47 of 50 instances were solved within ten minutes, versus 7 for the original model.
  • Regularization is competitive with tabulation and the two can be mixed: on Solitaire Battleships, combining regularized counting constraints with table constraints was the best configuration, improving average first-solution time by 60.8%.
  • Because the substitution is a preprocessing step, it can be combined with redundant modeling, parallel search, and parallel consistency techniques without interfering with them.
  • The performance of the replacement depends on how the sub-CSP is chosen; plain Regular was slower on Battleships, so detecting suitable sub-CSPs is essential for the approach to pay off.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension is to minimize the constructed DFA; standard automaton minimization could shrink the state set and make the regular constraint cheaper to propagate, an improvement the paper does not test.
  • The DFA size depends on the number of distinct prefixes rather than the number of full tuples, so regularization may scale better than tabulation when many solutions share long prefixes; this is consistent with the paper's closing intuition but its benchmarks do not demonstrate it.
  • The detection of sub-CSPs could be turned into a cost model that estimates enumeration time and automaton size against expected search savings, automating what the paper currently does with a heuristic.
  • The Battleships slowdown of plain Regular suggests a testable rule of thumb: regularization helps when the sub-CSP is small and its automaton stays small, and it hurts when a long variable sequence makes the automaton large or its propagation costly.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper proposes a preprocessing transformation for constraint satisfaction problems: a small sub-CSP is solved completely, all of its solutions are enumerated, and a deterministic finite automaton is constructed from the prefix sets of these solutions. The resulting regular constraint over the sub-CSP variables is then substituted for the original constraints of the sub-CSP. The authors argue that this strengthens propagation and reduces search effort, and they evaluate the idea on the Black Hole and Solitaire Battleships benchmarks against the original model and against table-constraint substitution. The construction itself is simple and mathematically transparent; the paper's central claim, however, is that the transformation improves solver speed in practice, and that claim rests on the experimental evaluation.

Significance. The DFA construction is sound: every transition is derived from a solution prefix, so the automaton accepts exactly the solution tuples of the enumerated sub-CSP, and replacing the sub-CSP constraints by the resulting regular constraint preserves the solution set of the full CSP. The approach has no fitted parameters and is not tuned to the benchmarks, and the comparison to the tabulation baseline is a useful reference point. If the empirical speedup claim were established, the method would be a simple and portable preprocessing technique for constraint solvers. However, the current experimental evidence is weakened by comparing averages over different solved-instance subsets, by relying on a manually combined variant for the strongest positive result, and by not measuring transformation times. The practical, automatic-preprocessing claim is therefore not yet fully supported.

major comments (4)
  1. [Section 4.1, Table 2] The average solution times appear to be computed only over instances solved by each model: the Original model solves 7 of 50 Black Hole instances, while the modified models solve 47. Comparing averages such as 516.432s versus 58.796s therefore mainly reflects that the modified models solve many more instances, not that they are faster on the same instances. The paper should report a paired comparison restricted to instances solved by all compared models, state explicitly how timeouts are treated in the averages, and give per-instance statistics rather than a single average that mixes different solved-instance subsets.
  2. [Section 4.2, Table 3 and Remark 3] In the Solitaire Battleships benchmark, the pure Regular variant is on average 11.6% slower than the Original model and is never the fastest on any of the 35 instances. The large reported average improvement of 60.8% comes from TableRegularIntersected, which combines table and regular constraints and, as Remark 3 states, was not computed fully automatically. Consequently this benchmark does not support the claim that the proposed transformation, applied automatically as a preprocessing step, improves solver speed; at best it indicates potential for a manually guided combination of tabulation and regularization.
  3. [Remark 4 (end of Section 4.2)] Transformation times are not measured; the paper only states that the total transformation time was less than three seconds for all Black Hole instances and less than four seconds for all Battleships instances, in comparison to 10- or 30-minute solution limits. Since the method is proposed as a preprocessing step, the transformation cost is part of the cost-benefit comparison and should be reported per instance and included in the reported total times rather than asserted to be negligible after the fact.
  4. [Section 3] Automatic detection of suitable sub-CSPs is explicitly deferred: the text states that 'an algorithm to detect such sub-CSPs must be developed in the future.' The experiments use the heuristic of [1] for Black Hole and manually indicated constraints for Battleships. The paper's stated goal of an automatic preprocessing transformation is therefore only partially realized in the evaluation. A revised version should either automate the detection for both benchmarks or clearly frame the contribution as a transformation whose automatic triggering remains open.
minor comments (4)
  1. [Table 3] Table 3 is titled 'Overwiev of the Black Hole bechmark' but it presents the Solitaire Battleships results; the title and the typo should be corrected.
  2. [Section 3, around Eqs. (3)-(7)] The equivalence between the constructed DFA and the original sub-CSP is never stated as a formal lemma. A short proof by induction on the prefix length would make the formal contribution self-contained and would make the correctness claim explicit.
  3. [Section 4.1] The 50 Black Hole instances are randomly generated, but no seeds or benchmark files are provided. Releasing the instances or the generator would allow reproducibility and would enable a fair paired re-evaluation.
  4. [Figures 1 and 2, footnote 2] The figures plot percentage improvements with negative values drawn at 1/10 of the real distance, which distorts the visual comparison. Plotting absolute solution times, or using a log scale, would give a more faithful picture of the per-instance behavior.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the DFA is constructed by exhaustive enumeration of sub-CSP solutions, so the regular constraint is equivalent to the replaced sub-CSP by construction; claimed speedups rest on external benchmarks, not on fitted inputs or load-bearing self-citations.

full rationale

The paper's central transformation is self-contained and non-circular. Given a sub-CSP Psub, the algorithm (Section 3) first solves Psub and enumerates its complete solution set S, then builds a DFA whose states are solution prefixes and whose accepting word set is exactly S (Equations 3-7). The resulting constraint regular(X', M) therefore accepts precisely the tuples satisfying C', making the replacement solution-set-preserving by construction rather than by appeal to a fitted parameter or an external theorem. The claimed performance improvements are empirical comparisons against the original model and the tabulation approach on two external benchmark suites (Black Hole and Solitaire Battleships); no parameter is tuned to produce the reported speedups, and no prediction is derived from data in a way that would make the evaluation circular. The paper does cite prior work by the same authors ([14], [15], [16]) for background on regular constraints and rCSPs, and [13] as one possible detection method, but none of these citations is load-bearing: the correctness of the presented DFA construction is established directly from the enumerated solutions, not from those references. The main weaknesses noted in the manuscript, such as Remark 3 (the TableRegularIntersected variant was not fully automatic) and Remark 4 (transformation times were not explicitly measured), concern the strength of the empirical evidence, not the logical dependence of the result on its inputs. Those issues belong to an experimental-validity discussion, not to circularity. Accordingly, the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central construction is self-contained and uses no fitted parameters and no invented entities. It relies on background CSP and regular-constraint semantics, on an external sub-CSP detection heuristic [1], on the practical assumption that full enumeration of the sub-CSP is fast, and on the informal assumption that transformation time is negligible.

assumptions (5)
  • domain assumption Sub-CSP detection heuristic from [1] identifies replaceable sub-CSPs for regular constraints.
    The paper relies on the weak-propagation heuristic of Akgun et al., which was designed for table constraints; no new detection algorithm is given (Section 3).
  • domain assumption All solutions of the sub-CSP can be enumerated in acceptable time.
    Remark 2 acknowledges NP-hardness but assumes smaller subproblems solve quickly; no time bound is proven, and the reported transformation times are informal.
  • domain assumption Regular constraint propagator in Choco maintains the same or stronger pruning than the original constraints.
    The paper assumes replacement preserves and may strengthen propagation, but it does not measure propagation strength directly (Sections 1 and 4).
  • ad hoc to paper Transformation time is negligible for the benchmark instances.
    Remark 4 states that transformation times were less than three or four seconds but were not explicitly recorded, yet they are used to justify ignoring preprocessing cost.
  • standard math Standard CSP, DFA and regular constraint semantics as background.
    Definitions from Dechter, Hopcroft and Ullman, and Pesant are cited and used in Section 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Regularization of Small Sub-Constraint Satisfaction Problems." pith.science (2026). https://pith.science/paper/QPKOLZ32

@misc{pith2026190805907,
  author       = {Pith},
  title        = {Pith review of: The Regularization of Small Sub-Constraint Satisfaction Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QPKOLZ32}},
  note         = {Machine review of arXiv:1908.05907}
}
read the original abstract

This paper describes a new approach on optimization of constraint satisfaction problems (CSPs) by means of substituting sub-CSPs with locally consistent regular membership constraints. The purpose of this approach is to reduce the number of fails in the resolution process, to improve the inferences made during search by the constraint solver by strengthening constraint propagation, and to maintain the level of propagation while reducing the cost of propagating the constraints. Our experimental results show improvements in terms of the resolution speed compared to the original CSPs and a competitiveness to the recent tabulation approach. Besides, our approach can be realized in a preprocessing step, and therefore wouldn't collide with redundancy constraints or parallel computing if implemented.

Figures

Figures reproduced from arXiv: 1908.05907 by the authors.

Figure 1
Figure 1. The time improvements (in %) of the Table, Regular and RegularIntersected models for finding the first solution of each instance of the Black Hole Problem in comparison to the Original model (0%) [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The time improvements (in %) of the Table, Regular, RegularIntersected and TableRegularIntersected models for finding the first solution of each instance of the Solitaire Battleships Problem in comparison to the Original model (0%) [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages

  1. [1]

    In: Principles and Practice of Constraint Programming - 24th In ternational Confer- ence, CP 2018, Lille, France, August 27-31, 2018, Proceedin gs

    Akg¨ un, ¨O., Gent, I.P., Jefferson, C., Miguel, I., Nightingale, P., S alamon, A.Z.: Automatic discovery and exploitation of promising subprob lems for tabulation. In: Principles and Practice of Constraint Programming - 24th In ternational Confer- ence, CP 2018, Lille, France, August 27-31, 2018, Proceedin gs. pp. 3–12 (2018), https://doi.org/10.1007/978-...

    work page doi:10.1007/978-3-319-98334-9_1 2018

  2. [2]

    In: de M´ antaras, R.L., Saitta, L

    Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boost ing systematic search by weighting constraints. In: de M´ antaras, R.L., Saitta, L . (eds.) Proceedings of the 16th Eureopean Conference on Artificial Intelligence, E CAI’2004, including Prestigious Applicants of Intelligent Systems, PAIS 2004, Valencia, Spain, August 22-27, 2004. pp. 146–150. IOS P...

    work page 2004

  3. [3]

    In: Freuder, E.C

    Cheng, B.M.W., Lee, J.H.M., Wu, J.C.K.: Speeding up const raint propagation by redundant modeling. In: Freuder, E.C. (ed.) Principles and Practice of Constraint Programming - CP96. pp. 91–103. Springer Berlin Heidelberg , Berlin, Heidelberg (1996)

    work page 1996

  4. [4]

    Elsevier Morgan Kau fmann (2003) 10 S

    Dechter, R.: Constraint processing. Elsevier Morgan Kau fmann (2003) 10 S. L¨ offler et al

    work page 2003

  5. [5]

    Constraints 22(4), 512–529 (2017), https://doi.org/10.1007/s10601-017-9270-5

    Dekker, J.J., Bj¨ ordal, G., Carlsson, M., Flener, P., Mon ette, J.: Auto-tabling for subproblem presolving in minizinc. Constraints 22(4), 512–529 (2017), https://doi.org/10.1007/s10601-017-9270-5

    work page doi:10.1007/s10601-017-9270-5 2017

  6. [6]

    http://www.csplib.org/Problems/prob014, last visited on 2019-05-07

    Gent, I.: CSPLib problem 014: Solitaire battleships. http://www.csplib.org/Problems/prob014, last visited on 2019-05-07

    work page 2019

  7. [7]

    AI Communications 20(3), 211–226 (2007), http://content.iospress.com/articles/ai-communications/aic405

    Gent, I.P., Jefferson, C., Kelsey, T., Lynce, I., Miguel, I ., Nightingale, P., Smith, B.M., Tarim, A.: Search in the patie nce game ’black hole’. AI Communications 20(3), 211–226 (2007), http://content.iospress.com/articles/ai-communications/aic405

    work page 2007

  8. [8]

    Journal of Experimental Algorithmics (JEA) 13 (2008)

    Gottlob, G., Samer, M.: A backtracking-based algorithm f or hypertree decompo- sition. Journal of Experimental Algorithmics (JEA) 13 (2008)

    work page 2008

Show all 22 references
  1. [9]

    Const raints 7(3-4), 367–385 (2002), https://doi.org/10.1023/A:1020594125144

    Hamadi, Y.: Optimal distributed arc-consistency. Const raints 7(3-4), 367–385 (2002), https://doi.org/10.1023/A:1020594125144

    2002 doi

  2. [10]

    In: Wallace, M

    Hellsten, L., Pesant, G., van Beek, P.: A domain consiste ncy algorithm for the stretch constraint. In: Wallace, M. (ed.) Principles and Pr actice of Constraint Pro- gramming - CP 2004. Lecture Notes in Computer Science, vol. 3 258, pp. 290–304. Springer (2004)

    2004

  3. [11]

    Addison-Wesley (1979)

    Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)

    1979

  4. [12]

    Con- straints 16(4), 341–371 (2011), https://doi.org/10.1007/s10601-011-9107-6

    Lecoutre, C.: STR2: optimized simple tabular reduction for table constraints. Con- straints 16(4), 341–371 (2011), https://doi.org/10.1007/s10601-011-9107-6

    2011 doi

  5. [13]

    Liu, K., L¨ offler, S., Hofstedt, P.: Hypertree decomposit ion: The first step towards parallel constraint solving. In: Declarative Programming and Knowledge Manage- ment - Conference on Declarative Programming, DECLARE 2017 , Unifying INAP, WFLP, and WLP, W¨ urzburg, Germany, Se...

    2017 doi

  6. [14]

    L¨ offler, S., Liu, K., Hofstedt, P.: The power of regular co nstraints in csps. In: 47. Jahrestagung der Gesellschaft f¨ ur Informati k, Informatik 2017, Chemnitz, Germany, September 25-29, 2017. pp. 603–61 4 (2017), https://doi.org/10.18420/in2017_57

    2017 doi

  7. [15]

    In: Artificial Intel ligence Applica- tions and Innovations - 14th IFIP WG 12.5 International Conf erence, AIAI 2018, Rhodes, Greece, May 25-27, 2018, Proceedings

    L¨ offler, S., Liu, K., Hofstedt, P.: The regularization of csps for rostering, plan- ning and resource management problems. In: Artificial Intel ligence Applica- tions and Innovations - 14th IFIP WG 12.5 International Conf erence, AIAI 2018, Rhodes, Greece, May 25-27, 2018, Proc...

    2018 doi

  8. [16]

    In: Rocha, A.P., Steels, L., van den Herik, J

    L¨ offler, S., Liu, K., Hofstedt, P.: A meta constraint sati sfaction optimiza- tion problem for the optimization of regular constraint sat isfaction prob- lems. In: Rocha, A.P., Steels, L., van den Herik, J. (eds.) Pr oceed- ings of the 11th International Conference on Agents a...

    2019

  9. [17]

    http://www.csplib.org/Problems/prob081, last visited on 2019-05-07

    Nightingale, P.: CSPLib problem 081: Black hole. http://www.csplib.org/Problems/prob081, last visited on 2019-05-07

    2019

  10. [18]

    In: Walsh, T

    Pesant, G.: A filtering algorithm for the stretch constra int. In: Walsh, T. (ed.) Principles and Practice of Constraint Programming - CP 2001 . Lecture Notes in Computer Science, vol. 2239, pp. 183–195. Springer (2001)

    2001

  11. [19]

    In: Wallace, M

    Pesant, G.: A regular language membership constraint fo r finite sequences of vari- ables. In: Wallace, M. (ed.) Principles and Practice of Cons traint Programming - CP 2004. Lecture Notes in Computer Science, vol. 3258, pp. 4 82–495. Springer (2004) The Regularization of sub-CSPs 11

    2004

  12. [20]

    TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S

    Prud’homme, C., Fages, J.G., Lorca, X.: Choco Documenta tion. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S. (2016), http://www.choco-solver.org/, last visited 2019-05-07

    2016

  13. [21]

    In: Schulte, C

    R´ egin, J.C., Rezgui, M., Malapert, A.: Embarrassingly parallel search. In: Schulte, C. (ed.) Principles and Practice of Constraint Programming . pp. 596–610. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)

    2013

  14. [2019]

    pp. 435–442. SciTePress (2019). https://doi.org/10 .5220/0007260204350442, https://doi.org/10.5220/0007260204350442

    2019 doi

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.