Propagating lex, find and replace with dashed strings. (English) Zbl 06982381

Amadini, Roberto; Gange, Graeme; Stuckey, Peter J.

van Hoeve, Willem-Jan (ed.), Integration of constraint programming, artificial intelligence, and operations research. 15th international conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-93030-5/pbk; 978-3-319-93031-2/ebook). Lecture Notes in Computer Science 10848, 18-34 (2018).

Summary: Dashed strings have been recently proposed in constraint programming to represent the domain of string variables when solving combinatorial problems over strings. This approach showed promising performance on some classes of string problems, involving constraints like string equality and concatenation. However, there are a number of string constraints for which no propagator has yet been defined. In this paper, we show how to propagate lexicographic ordering (lex), find and replace with dashed strings. All of these are fundamental string operations: lex is the natural total order over strings, while find and replace are frequently used in string manipulation. We show that these propagators, that we implemented in G-Strings solver, allows us to be competitive with state-of-the-art approaches.
For the entire collection see [Zbl 1388.68011].

MSC:

68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27	Combinatorial optimization

Software:

Gecode; HAMPI; MiniZinc; PASS; StrSolve; WAPTEC; Z3str3