Propagating lex, find and replace with dashed strings

Roberto Amadini; Graeme Gange; Peter J. Stuckey

doi:10.1007/978-3-319-93031-2_2

Propagating lex, find and replace with dashed strings

Roberto Amadini, Graeme Gange, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

7 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 language	English
Title of host publication	Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Subtitle of host publication	15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings
Editors	Willem-Jan van Hoeve
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	18-34
Number of pages	17
ISBN (Electronic)	9783319930312
ISBN (Print)	9783319930305
DOIs	https://doi.org/10.1007/978-3-319-93031-2_2
Publication status	Published - 2018
Externally published	Yes
Event	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018 - Delft, Netherlands Duration: 26 Jun 2018 → 29 Jun 2018 Conference number: 15th https://sites.google.com/view/cpaior2018 (Conference website) https://link.springer.com/book/10.1007/978-3-319-93031-2 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10848
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018
Abbreviated title	CPAIOR 2018
Country/Territory	Netherlands
City	Delft
Period	26/06/18 → 29/06/18
Internet address	https://sites.google.com/view/cpaior2018 (Conference website) https://link.springer.com/book/10.1007/978-3-319-93031-2 (Proceedings)

Access to Document

10.1007/978-3-319-93031-2_2

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

Amadini, Roberto ; Gange, Graeme ; Stuckey, Peter J. / Propagating lex, find and replace with dashed strings. Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings. editor / Willem-Jan van Hoeve. Cham Switzerland : Springer, 2018. pp. 18-34 (Lecture Notes in Computer Science ).

@inproceedings{0e34c7fbf901483db78e1c9fdf128cee,

title = "Propagating lex, find and replace with dashed strings",

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.",

author = "Roberto Amadini and Graeme Gange and Stuckey, {Peter J.}",

year = "2018",

doi = "10.1007/978-3-319-93031-2_2",

language = "English",

isbn = "9783319930305",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "18--34",

editor = "{van Hoeve}, Willem-Jan",

booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research",

note = "International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018, CPAIOR 2018 ; Conference date: 26-06-2018 Through 29-06-2018",

url = "https://sites.google.com/view/cpaior2018, https://link.springer.com/book/10.1007/978-3-319-93031-2",

}

Amadini, R, Gange, G & Stuckey, PJ 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. Lecture Notes in Computer Science , vol. 10848 , Springer, Cham Switzerland, pp. 18-34, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018, Delft, Netherlands, 26/06/18. https://doi.org/10.1007/978-3-319-93031-2_2

Propagating lex, find and replace with dashed strings. / Amadini, Roberto; Gange, Graeme; Stuckey, Peter J.
Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings. ed. / Willem-Jan van Hoeve. Cham Switzerland: Springer, 2018. p. 18-34 (Lecture Notes in Computer Science ; Vol. 10848 ).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Propagating lex, find and replace with dashed strings

AU - Amadini, Roberto

AU - Gange, Graeme

AU - Stuckey, Peter J.

N1 - Conference code: 15th

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85048604852&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-93031-2_2

DO - 10.1007/978-3-319-93031-2_2

M3 - Conference Paper

AN - SCOPUS:85048604852

SN - 9783319930305

T3 - Lecture Notes in Computer Science

SP - 18

EP - 34

BT - Integration of Constraint Programming, Artificial Intelligence, and Operations Research

A2 - van Hoeve, Willem-Jan

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2018

Y2 - 26 June 2018 through 29 June 2018

ER -

Amadini R, Gange G, Stuckey PJ. Propagating lex, find and replace with dashed strings. In van Hoeve WJ, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018 Delft, The Netherlands, June 26–29, 2018 Proceedings. Cham Switzerland: Springer. 2018. p. 18-34. (Lecture Notes in Computer Science ). doi: 10.1007/978-3-319-93031-2_2

Propagating lex, find and replace with dashed strings

Abstract

Publication series

Conference

Access to Document

Other files and links

Towards reliability in combinatorial optimisation

Cite this

Propagating lex, find and replace with dashed strings

Abstract

Publication series

Conference

Access to Document

Other files and links

Projects

Towards reliability in combinatorial optimisation

Cite this