You are here

Randomness as a Constraint

Authors: 

Steven Prestwich, Roberto Rossi, Armagan Tarim

Publication Type: 
Refereed Conference Meeting Proceeding
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.
Conference Name: 
International Conference on Principles and Practice of Constraint Programming
Digital Object Identifer (DOI): 
in press
Publication Date: 
16/09/2015
Conference Location: 
Ireland
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: