Solver-Aided Expansion of Loops to Avoid Generate-and-Test

Niklas Dewally, Özgür Akgün · 2025

Read Solver-Aided Expansion of Loops to Avoid Generate-and-Test by Niklas Dewally, Özgür Akgün (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08442.txt.

Introduction

Niklas Dewally and Özgür Akgün present a 2025 arXiv paper on compiling constraint models faster. Languages like MiniZinc unroll loops at compile time, generating every combination and throwing most away, which crawls when ranges are huge. Their method asks a solver up front which combinations the final constraints actually need, and expands only those.

The output model is identical to the standard one, so answers never change. Compilation, though, can speed up sharply, above all where large domains meet narrow preconditions. The authors pitch solver-aided expansion as a drop-in win for translating high-level models into solver-ready form.

Catalog record

CREATORNiklas Dewally, Özgür Akgün
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08442

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solver-Aided Expansion of Loops to Avoid Generate-and-Test Niklas Dewally, Özgür Akgün Abstract Constraint modelling languages like MiniZinc and Essence rely on unrolling loops (in the form of quantified expressions and comprehensions) during compilation. Standard approaches generate all combinations of induction variables and use partial evaluation to discard those that simplify to identity elements of associative-commutative operators (e.g. true for conjunction, 0 for summation). This can be inefficient for problems where most combinations are ultimately irrelevant. We present a method that avoids full enumeration by using a solver to compute only the combinations required to generate the final set of constraints. The resulting model is identical to that produced by conventional flattening, but compilation can be significantly faster. This improves the efficiency of translating high-level user models into solver-ready form, particularly when induction variables range over large domains with selective preconditions. School of Computer Science, University of St Andrews, UK and https://niklas.dewally.com/ [email protected]://orcid.org/0009-0004-6662-020X School of Computer Science, University of St Andrews, UK and https://www.st-andrews.ac.uk/computer-science/people/oa86 [email protected]://orcid.org/0000-0001-9519-938X We thank the members of the “AI for Decision Making” Vertically Integrated Project at the University of St Andrews for their contributions. keywords Constraint modelling, Loop unrolling, Solver-aided reformulation ccs Computing methodologies Artificial intelligence † † runningtitle: Solver-Aided Expansion of Loops to Avoid Generate-and-Test † † runningauthor: N, Dewally, Ö. Akgün † † supplement: Our prototype extension to Conjure is available at https://github.com/conjure-cp/conjure-oxide . The models we use in our experiments, scripts we use to run the experiments, raw results and plotting scripts are available at https://github.com/niklasdewally/2025-comprehension-unrolling-modref . † † supplement: Software: https://doi.org/10.5281/zenodo.16723727 † † supplement: Dataset: https://doi.org/10.5281/zenodo.16724771 † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Constraint modelling languages such as Essence [ 1 ] , Essence Prime [ 4 ] , and MiniZinc [ 3 ] allow users to specify complex combinatorial problems in a concise and declarative manner. However, the efficiency of compiling these models often hinges on how loops and quantified expressions are expanded, minor syntactic changes can lead to substantial differences in compilation time and memory use. Current tools rely on generate-and-test strategies combined with partial evaluation, making performance fragile and dependent on modeller expertise. We present a solver-aided method for expanding comprehensions and quantified expressions that is robust to syntactic formulation. Our approach eliminates the need for full enumeration and partial evaluation, ensuring that only relevant combinations of induction variables are generated, regardless of how guards or conditions are expressed. This step moves declarative modelling closer to its ideal: enabling users to express intent without hidden performance traps. The underlying technique is general and could be adapted for any context where side-effect-free loop unrolling is required. Empirical results on standard benchmarks demonstrate that our solver-aided expansion method robustly scales across different syntactic formulations of constraints. It significantly reduces compilation times compared to traditional generate-and-test approaches, particularly when implicit conditions or large domains are involved. This robustness and efficiency makes constraint model compilation more reliable, allowing users to express intent clearly without concern for hidden performance costs. 2 Motivation Efficient unrolling of loops, quantified expressions, and comprehensions is critical in constraint modelling languages such as MiniZinc and Essence Prime , as it directly affects the scalability and performance of model compilation. Typically, these languages expand loops into explicit constraints through generate-and-test strategies, enumerating all combinations and subsequently filtering irrelevant cases. \captionsetup [subfigure]justification=centering {subfigure} [t] {lstlisting} [] int: n; array[1..n] of var 1..2: class; constraint forall(a,b,c in 1..n)( (a¡=b / b¡=c / a^2 + b^2 = c^2) -¿ ( class[a] != class[b] class[b] != class[c] class[c] != class[a])); solve satisfy; Figure 1: Naive MiniZinc model. As an indicative figure, this model takes 7.8 seconds to translate, with n=200 . {subfigure} [t] {lstlisting} [] int: n; array[1..n] of var 1..2: class; constraint forall(a,b,c in 1..n)( if (a¡=b / b¡=c / a^2 + b^2 = c^2) then (class[a] != class[b] class[b] != class[c] class[c] != class[a]) else true endif); solve satisfy; Figure 2: Another MiniZinc model using an if statement. As an indicative figure, this model takes 15.3 seconds to translate, with n=200 . {subfigure} [t] {lstlisting} [] int: n; array[1..n] of var 1..2: class; constraint forall(x in [ class[a] != class[b] class[b] != class[c] class[c] != class[a] — a,b,c in 1..n where (a¡=b / b¡=c / a^2 + b^2 = c^2) ])(x); solve satisfy; Figure 3: Faster MiniZinc model using a static comprehension guard. As an indicative figure, this model takes 1.3 seconds to translate, with n=200 . Figure 4: MiniZinc models of the Boolean Pythagorean Triples Problem To illustrate, consider the Boolean Pythagorean Triples Problem [ 2 ] , a well-known constraint satisfaction problem that partitions integers into two classes such that no Pythagorean triple (a,b,c) lies entirely within a single class. A natural MiniZinc formulation of this problem ( Figure 4 ) explicitly loops through all possible triples (a,b,c) , creating constraints for each combination. Although intuitive, this approach scales poorly: MiniZinc takes approximately 1.07 seconds for n=100 and dramatically increases to 7.82 seconds at n=200 , due to enumerating and evaluating all n^{3} combinations. Using an if statement instead of a logical implication as in Figure 4 roughly doubles the time taken. In contrast, adding a simple comprehension guard drastically improves MiniZinc ’s compilation time. Figure 4 , which filters combinations explicitly through a comprehension guard, compiles significantly faster (1.28 seconds for n=200 ), despite being semantically equivalent to the original formulation. This performance discrepancy highlights how subtle modelling differences critically impact practical usability. \captionsetup [subfigure]justification=centering {subfigure} [t] {lstlisting} [language=Python] triples = [] for a in range(1, n+1): for b in range(1, n+1): for c in range(1, n+1): if a ¡= b ¡= c and a ** 2 + b ** 2 == c ** 2: triples.append([a,b,c]) Figure 5: Naive Python implementation. For n=1000 , this program takes roughly 3 minutes to run. {subfigure} [t] {lstlisting} [language=Python] triples = [] for a in range(1, n+1): for b in range(a, n+1): c_squared = a**2 + b**2 c = int(c_squared ** 0.5) if c ¡ b or c ¿ n: continue if c**2 == c_squared: triples.append([a, b, c]) Figure 6: Optimised Python implementation. For n=1000 , this program takes less than a second to run. Figure 7: Python enumeration of the relevant triples for the Boolean Pythagorean Triples Problem Such issues are not exclusive to constraint modelling languages. A naive implementation of triple generation in Python ( Figure 7 ) also enumerates all possibilities and performs poorly, taking roughly two minutes for n=1000 . While an optimised Python version ( Figure 7 ) is faster, it requires manual optimisation and increased complexity, contradicting the simplicity and clarity benefits provided by declarative languages. \captionsetup [subfigure]justification=centering {subfigure} [t] {lstlisting} given n: int(1..) find class: matrix indexed by [int(1..n)] of int(1..2) such that forAll a,b,c: int(1..n). (a**2 + b**2 = c**2 / a¡=b / b¡=c) -¿ or([class[a] != class[b], class[b] != class[c], class[c] != class[a]]) Figure 8: Using a forall quantified expression. As an indicative figure, this

Read the complete text