Randomness as a constraint

Steven D Prestwich, Roberto Rossi, S. Armagan Tarim

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

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.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publicationProceedings of the 21st International Conference, CP 2015, Cork, Ireland, August 31 - September 4, 2015
EditorsGilles Pesant
PublisherSpringer-Verlag
Pages351-366
ISBN (Electronic)9783319232195
ISBN (Print)9783319232188
DOIs
Publication statusPublished - 2015
Event21st International Conference on Principles and Practice of Constraint Programming (CP 2015) - Cork, Ireland
Duration: 31 Aug 20154 Sep 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume9255

Conference

Conference21st International Conference on Principles and Practice of Constraint Programming (CP 2015)
Country/TerritoryIreland
CityCork
Period31/08/154/09/15

Fingerprint

Dive into the research topics of 'Randomness as a constraint'. Together they form a unique fingerprint.

Cite this