MiniZinc with Strings

Roberto Amadini, Pierre Flener, Justin Pearson, Joseph D. Scott, Peter J. Stuckey, Guido Tack

Abstract: Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no CP solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying on only integer variables. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.

Introduction

Strings are the backbone of modern computing, yet they are notoriously difficult to reason about in formal logic. In fields like software analysis, test-case generation, and web security (e.g., detecting SQL injection), researchers need to solve constraints over strings of unknown lengths. While specialized "string solvers" exist, the broader Constraint Programming (CP) community has largely lacked a unified way to model these problems. Most CP solvers are designed for integers and real numbers. Before this work, using a powerful CP solver like Gecode or Chuffed on a string problem required manually translating every string operation into complex integer arrays—a tedious and error-prone process.

Language Extensions and Modeling

The authors propose a two-pronged extension to the MiniZinc ecosystem. First, they introduced var string as a first-class citizen in MiniZinc. This includes a library of standard functions: concatenation (++), length (str_len), sub-string selection, and even complex constraints like Regular Expression (DFA/NFA) membership and Global Cardinality (counting character occurrences).

Table 1: Overview of the new string constraints introduced in MiniZinc, showing the mathematical notation, the MiniZinc syntax, and a brief description.

The $\mathcal{F}^{int}$ Transformation

The second part of the extension is the "magic" under the hood: the $\mathcal{F}^{int}$ transformation. For solvers that do not support strings natively, MiniZinc now includes a library that automatically "flattens" string variables into arrays of integers (representing ASCII codes).

  • Padding & Length: Since MiniZinc arrays usually have fixed sizes, the authors use an "open-sequence" representation. A string is mapped to an array of length $L$ (the maximum possible length), an integer variable for the actual length, and "trailing zeros" to pad the unused space.
  • Automata Tweaking: To handle regular expression constraints (DFAs) on these padded arrays, they developed a method to modify the automaton so it correctly ignores the padding characters.

Experimental Evaluation

The framework was evaluated using the Norn Benchmark (a set of five challenging problems: anb_n, ChunkSplit, HammingDistance, Levenshtein, and StringReplace) and a custom Palindrome Problem designed to find the minimum-length palindrome with specific character counts.

Table 2: Performance results (in seconds) for various solvers across different benchmarks and string lengths ($\ell$). 't/o' indicates a timeout, and 'n/a' indicates the solver does not support the constraint.

Key Results and Insights

  • Native vs. Decomposed: Gecode+S (which has native string support) was generally the fastest and most robust across the board. However, on certain benchmarks like the Palindrome problem, solvers using the $\mathcal{F}^{int}$ decomposition (like Chuffed and iZplus) actually outperformed native solvers in search speed.
  • The Flattening Bottleneck: A significant finding is that the bottleneck isn't always the solving time, but the compilation time. Turning a single string constraint into thousands of integer constraints for a long string can result in massive FlatZinc files (e.g., jumping from 14 lines to 45,000 lines).
  • Scalability: The framework successfully handled string lengths up to 1,000 characters, though performance degrades as the maximum bound increases due to the quadratic growth of some decomposed constraints.

Conclusion and Future Work

This work proves that "Model Once, Solve Anywhere" is now a reality for strings in MiniZinc. While currently limited to the ASCII character set and requiring a fixed maximum length ($L$), the framework allows general-purpose solvers to leverage advanced search heuristics like "lazy clause generation" for string problems. Future work will focus on extending support to Unicode and developing "string-aware" search heuristics to further improve efficiency.

Summary updated

Abstract

Strings are extensively used in modern programming languages and constraints over strings of unknown length occur in a wide range of real-world applications such as software analysis and verification, testing, model checking, and web security. Nevertheless, practically no CP solver natively supports string constraints. We introduce string variables and a suitable set of string constraints as builtin features of the MiniZinc modelling language. Furthermore, we define an interpreter for converting a MiniZinc model with strings into a FlatZinc instance relying on only integer variables. This provides a user-friendly interface for modelling combinatorial problems with strings, and enables both string and non-string solvers to actually solve such problems.
BibTeX
@inproceedings{amadini2016minizinc,
  author = {Roberto Amadini and Pierre Flener and Justin Pearson and Joseph D. Scott and Peter J. Stuckey and Guido Tack},
  title = {{MiniZinc with Strings}},
  booktitle = {LOPSTR},
  year = {2016},
  doi = {10.1007/978-3-319-63139-4\_4},
}
Figure