Randomness as a constraint

Steven D Prestwich; Roberto Rossi; S. Armagan Tarim

doi:10.1007/978-3-319-23219-5_25

Randomness as a constraint

Steven D Prestwich, Roberto Rossi, S. Armagan Tarim

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

Abstract / Description of output

Some optimisation problems require a random-looking solution with no apparent patterns, for reasons of fairness, anonymity, undetectability or unpredictability. Randomised search is not a good general approach because problem constraints and objective functions may lead to solutions that are far from random.We propose a constraint-based approach to finding pseudo-random solutions, inspired by the Kolmogorov complexity definition of randomness and by data compression methods.Our “entropy constraints” can be implemented in constraint programming systems using well-known global constraints. We apply them to a problem from experimental psychology and to a factory inspection problem.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	Proceedings of the 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015
Editors	Gilles Pesant
Publisher	Springer
Pages	351-366
ISBN (Electronic)	9783319232195
ISBN (Print)	9783319232188
DOIs	https://doi.org/10.1007/978-3-319-23219-5_25
Publication status	Published - 2015
Event	21st International Conference on Principles and Practice of Constraint Programming (CP 2015) - Cork, Ireland Duration: 31 Aug 2015 → 4 Sept 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	9255

Conference

Conference	21st International Conference on Principles and Practice of Constraint Programming (CP 2015)
Country/Territory	Ireland
City	Cork
Period	31/08/15 → 4/09/15

Access to Document

10.1007/978-3-319-23219-5_25

21st International Conference on Principles and Practice of Constraint Programming (CP 2015)
Roberto Rossi (Participant)
2015
Activity: Participating in or organising an event types › Participation in conference

Cite this

Prestwich, S. D., Rossi, R., & Armagan Tarim, S. (2015). Randomness as a constraint. In G. Pesant (Ed.), Principles and Practice of Constraint Programming: Proceedings of the 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015 (pp. 351-366). (Lecture Notes in Computer Science; Vol. 9255). Springer. https://doi.org/10.1007/978-3-319-23219-5_25

@inbook{6ce1e69e02a1444ebf0a21d8e975f6ab,

title = "Randomness as a constraint",

abstract = "Some optimisation problems require a random-looking solution with no apparent patterns, for reasons of fairness, anonymity, undetectability or unpredictability. Randomised search is not a good general approach because problem constraints and objective functions may lead to solutions that are far from random.We propose a constraint-based approach to finding pseudo-random solutions, inspired by the Kolmogorov complexity definition of randomness and by data compression methods.Our “entropy constraints” can be implemented in constraint programming systems using well-known global constraints. We apply them to a problem from experimental psychology and to a factory inspection problem.",

author = "Prestwich, {Steven D} and Roberto Rossi and {Armagan Tarim}, S.",

year = "2015",

doi = "10.1007/978-3-319-23219-5_25",

language = "English",

isbn = "9783319232188",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "351--366",

editor = "Pesant, {Gilles }",

booktitle = "Principles and Practice of Constraint Programming",

note = "21st International Conference on Principles and Practice of Constraint Programming (CP 2015) ; Conference date: 31-08-2015 Through 04-09-2015",

}

Prestwich, SD, Rossi, R & Armagan Tarim, S 2015, Randomness as a constraint. in G Pesant (ed.), Principles and Practice of Constraint Programming: Proceedings of the 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015. Lecture Notes in Computer Science, vol. 9255, Springer, pp. 351-366, 21st International Conference on Principles and Practice of Constraint Programming (CP 2015), Cork, Ireland, 31/08/15. https://doi.org/10.1007/978-3-319-23219-5_25

Randomness as a constraint. / Prestwich, Steven D; Rossi, Roberto; Armagan Tarim, S.
Principles and Practice of Constraint Programming: Proceedings of the 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015. ed. / Gilles Pesant. Springer, 2015. p. 351-366 (Lecture Notes in Computer Science; Vol. 9255).

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

TY - CHAP

T1 - Randomness as a constraint

AU - Prestwich, Steven D

AU - Rossi, Roberto

AU - Armagan Tarim, S.

PY - 2015

Y1 - 2015

N2 - Some optimisation problems require a random-looking solution with no apparent patterns, for reasons of fairness, anonymity, undetectability or unpredictability. Randomised search is not a good general approach because problem constraints and objective functions may lead to solutions that are far from random.We propose a constraint-based approach to finding pseudo-random solutions, inspired by the Kolmogorov complexity definition of randomness and by data compression methods.Our “entropy constraints” can be implemented in constraint programming systems using well-known global constraints. We apply them to a problem from experimental psychology and to a factory inspection problem.

AB - Some optimisation problems require a random-looking solution with no apparent patterns, for reasons of fairness, anonymity, undetectability or unpredictability. Randomised search is not a good general approach because problem constraints and objective functions may lead to solutions that are far from random.We propose a constraint-based approach to finding pseudo-random solutions, inspired by the Kolmogorov complexity definition of randomness and by data compression methods.Our “entropy constraints” can be implemented in constraint programming systems using well-known global constraints. We apply them to a problem from experimental psychology and to a factory inspection problem.

U2 - 10.1007/978-3-319-23219-5_25

DO - 10.1007/978-3-319-23219-5_25

M3 - Chapter (peer-reviewed)

SN - 9783319232188

T3 - Lecture Notes in Computer Science

SP - 351

EP - 366

BT - Principles and Practice of Constraint Programming

A2 - Pesant, Gilles

PB - Springer

T2 - 21st International Conference on Principles and Practice of Constraint Programming (CP 2015)

Y2 - 31 August 2015 through 4 September 2015

ER -

Randomness as a constraint

Abstract / Description of output

Publication series

Conference

Access to Document

Fingerprint

Activities

21st International Conference on Principles and Practice of Constraint Programming (CP 2015)

Cite this