Design and Implementation of Bounded-Length Sequence Variables
Joseph D. Scott, Pierre Flener, Justin Pearson, Christian Schulte.
We present the design and implementation of bounded-length sequence (BLS) variables for a CP solver. The domain of a BLS variable is represented as the combination of a set of candidate lengths and a sequence of sets of candidate characters. We show how this choice of representation, together with requirements imposed by propagators, affects the implementation of BLS variables for a modern CP copying solver, most importantly the closely related decisions of data structure, domain restriction operations, and propagation events. The resulting implementation outperforms traditional bounded-length string representations for finite-domain solvers, which use a fixed-length array of candidate characters and a padding symbol. The performance improvement on benchmark problems is significant.
In: Domenico Salvagnin, Michele Lombardi, editors, Fourteenth International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, Padova, Italy, Lecture Notes in Computer Science, pages 51-67. Springer-Verlag, June, 2017. DOI 10.1007/978-3-319-59776-8_5.
Copyright Springer-Verlag, the original publication is available at www.springerlink.com