Title: A pre-processing algorithm for solving constraint satisfaction optimisation problems
Abstract: A constraint satisfaction problem (CSP) involves finding values, selected from a finite domain, for all variables such that all constraints on the variables are satisfied. A constraint satisfaction optimisation problem (CSOP) is a CSP that has some objective function defined in terms of some or all of the variables. We present an algorithm where we employ local consistency techniques in a pre-processing phase, in order to decrease the domain sizes of the variables. This results in a simplified CSOP to be solved by an existing algorithm.Partial constraint satisfaction involves finding values for all variables such that a maximal subset of the constraints is satisfied. We expand our pre-processing algorithm to the partial CSOP case.
Publication Year: 2003
Publication Date: 2003-09-17
Language: en
Type: article
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot