Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Function Variables for Constraint Programming
Uppsala University, Humanistisk-samhällsvetenskapliga vetenskapsområdet, Faculty of Social Sciences, Department of Information Science.
2003 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

Quite often modelers with constraint programming (CP) use the same modelling patterns for different problems, possibly from different domains. This results in recurring idioms in constraint programs. Our approach can be seen as a three-step approach. First, we identify some of these recurring patterns in constraint programs. Second, we propose a general way of describing these patterns by introducing proper constructs that would cover a wide range of applications. Third, we propose automating the process of reproducing these idioms from these higher-level descriptions. The whole process can be seen as a way of encapsulating some of the expertise and knowledge often used by CP modelers and making it available in much simpler forms. Doing so, we are able to extend current CP languages with high-level abstractions that open doors for automation of some of the modelling processes.

In particular, we introduce function variables and allow the statement of constraints on these variables using function operations. A function variable is a decision variable that can take a value from a set of functions as opposed to an integer variable that ranges over integers, or a set variable that ranges over a set of sets. 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 function model expressed using function variables opens doors to the automatic generation of alternate CP models. These alternate models either use a different variable representation, or have extra implied constraints, or employ different constraint formulation, or combine different models that are linked using channelling constraints. A number of heuristics are also developed that allow the comparison of different constraint formulations. Furthermore, we present an extensive theoretical comparison of models of injection problems supported by asymptotic and empirical studies. Finally, a practical modelling tool that is built based on a high-level language that allows function variables is presented and evaluated. The tool helps users explore different alternate CP models starting from a function model that is easier to develop, understand, and maintain.

Place, publisher, year, edition, pages
Uppsala: Institutionen för informationsvetenskap , 2003. , p. 156
Keyword [en]
Datalogi, Constraint saisfaction, constraint programming, high-level modelling, abstraction, reformulation, function variables.
Keyword [sv]
Datalogi
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-3143ISBN: 91-506-1650-1 (print)OAI: oai:DiVA.org:uu-3143DiVA, id: diva2:162235
Public defence
2003-01-17, Lecture Hall 2, Ekonomikum,, Uppsala, 13:15
Opponent
Available from: 2002-12-16 Created: 2002-12-16 Last updated: 2018-01-13Bibliographically approved

Open Access in DiVA

fulltext(763 kB)1887 downloads
File information
File name FULLTEXT01.pdfFile size 763 kBChecksum SHA-1
812b8d80469d93ee1eef1537bbdd00638220466079c1945a1e901dda60bd83ae8cb248a2
Type fulltextMimetype application/pdf

By organisation
Department of Information Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1887 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 962 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf