Function variables for constraint programming

Article type: Other

Authors: Hnich, Brahim

Affiliations: Computer Science Division, Department of Information Science, Uppsala University, Sweden E‐mail: brahim@4c.ucc.ie

Abstract: We introduce function variables to constraint programs (CP), variables whose values are one of (exponentially many) possible functions between two sets. Such variables are useful for modelling problems from domains such as configuration, planning, scheduling, etc. We show that a function variable can be mapped into different representations in terms of integer and set variables, and illustrate how to map constraints stated on a function variable into constraints on integer and set variables. As a result, a constraint model expressed using function variables allows for the generation of alternate CP models. Furthermore, we present an extensive theoretical comparison of models of problems involving injective functions supported by asymptotic and empirical studies. Finally, we present and evaluate a practical modelling tool that is based on a high‐level language that supports function variables. The tool helps users explore different alternate CP models starting from a function model that is easy to develop, understand, and maintain.

Keywords: Constraint satisfaction, constraint programming, high‐level modelling, abstraction, reformulation, function variables

Journal: AI Communications, vol. 16, no. 2, pp. 131-132, 2003