TY - GEN
T1 - Randomness as a constraint
AU - Prestwich, Steven D.
AU - Rossi, Roberto
AU - Tarim, S. Armagan
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
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 constraintbased 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 constraintbased 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.
UR - https://www.scopus.com/pages/publications/84944528814
UR - https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=performanshacettepe&SrcAuth=WosAPI&KeyUT=WOS:000364707100025&DestLinkType=FullRecord&DestApp=WOS_CPL
U2 - 10.1007/978-3-319-23219-5_25
DO - 10.1007/978-3-319-23219-5_25
M3 - Conference contribution
AN - SCOPUS:84944528814
SN - 9783319232188
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 351
EP - 366
BT - Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings
A2 - Pesant, Gilles
PB - Springer Verlag
T2 - 21st International Conference on the Principles and Practice of Constraint Programming, CP 2015
Y2 - 31 August 2015 through 4 September 2015
ER -