Boosting Open CSPs

Macho González, Santiago; Ansótegui Gil, Carlos José; Meseguer, Pedro

Visualitza/Obre

Postprint (215.2Kb)

Data de publicació

2006

Autor/a

Macho González, Santiago

Ansótegui Gil, Carlos José

Meseguer, Pedro

Citació recomanada

Macho González, Santiago; Ansótegui Gil, Carlos José; Meseguer, Pedro; . (2006) . Boosting Open CSPs. Lecture Notes in Computer Science, 2006, vol. 4204, p.314-328. http://hdl.handle.net/10459.1/62661.

Resum

In previous work, a new approach called Open CSP (OCSP) was defined as a way of integrate information gathering and problem solving. Instead of collecting all variable values before CSP resolution starts, OCSP asks for values dynamically as required by the solving process, starting from possibly empty

domains. This strategy permits to handle unbounded domains keeping completeness. However, current OCSP algorithms show a poor performance. For instance, the FO-Search algorithm uses a Backtracking and needs to solve the new problem from scratch every time a new value is acquired. In this paper we improve the original algorithm for the OCSP model. Our contribution is two-fold: we incorporate local consistency and we avoid solving subproblems already explored in previous steps. Moreover, these two contributions guarantee the completeness of the algorithm and they do not increase the number of values needed for finding a solution. We provide experimental results than confirm a significant speed-up on the original approach.