Exploring Alternative Restoration Techniques in Constraint Programming

Abstract

Constraint programming is a powerful tool for solving combinatorial problems, and constraint programming systems provide the facilities to support this tool. In such a system, search defines the strategies to explore solutions, and restoration recovers from an inconsistency to a previously visited state. Hence, a state-of-the-art restoration is essential for an efficient constraint programming system.

In this thesis, we investigate two alternative restoration techniques for building constraint programming systems. The first is to maintain the variables that were affected by propagation to reach fix points. It neither rolls back performed operations as trailing does nor repeats computation work as recomputation does, while consuming much less memory than copying. Subsequently, we explore programming restoration granularity, which aims at providing facilities for users to customize restoration, and describe a prototype implementation. Finally, we propose the use of the aspect-oriented programming paradigm to achieve a more extensible and modular system.