A central service of a constraint programming system is search. In almost all constraint
programming systems search is based on trailing,
which is well understood and known to be
efficient. This paper compares trailing to
copying. Copying offers more expressiveness as
required by parallel and concurrent
systems. However, little is known how trailing
compares to copying as it comes to implementation
effort, runtime efficiency, and memory
requirements. This paper discusses these issues.
Execution speed of a copying-based system is shown to be competitive with state-of-the-art trailing-based systems. For the first time, a detailed analysis and comparison with respect to memory usage is made. It is shown how recomputation decreases memory requirements which can be prohibitive for large problems with copying alone. The paper introduces an adaptive recomputation strategy that is shown to speedup search while keeping memory consumption low. It is demonstrated that copying with recomputation outperforms trailing on large problems with respect to both space and time.
Download PDF Show BibTeX
Login to edit
Wed Sep 16 10:47:00 2009