Propagating lex, find and replace with dashed strings

Roberto Amadini, Graeme Gange, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings
EditorsWillem-Jan van Hoeve
Place of PublicationCham Switzerland
PublisherSpringer
Pages18-34
Number of pages17
ISBN (Electronic)978-3-319-93031-2
ISBN (Print)9783319930305
DOIs
Publication statusPublished - 2018
Externally publishedYes
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018 - Delft, Netherlands
Duration: 26 Jun 201829 Jun 2018
Conference number: 15th
https://sites.google.com/view/cpaior2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10848
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018
Abbreviated titleCPAIOR 2018
CountryNetherlands
CityDelft
Period26/06/1829/06/18
Internet address

Cite this

Amadini, R., Gange, G., & Stuckey, P. J. (2018). Propagating lex, find and replace with dashed strings. In W-J. van Hoeve (Ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings (pp. 18-34). (Lecture Notes in Computer Science ; Vol. 10848 ). Springer. https://doi.org/10.1007/978-3-319-93031-2_2