Parallel execution models and algorithms for constraint logic programming over a real-number domain
Jennifer J. Burg · Journal of International Crisis and Risk Communication Research · 1992
CLP-$\Re$ is a constraint logic programming language with the ability to handle linear real-number constraints. We present a new incremental variation of Gaussian elimination and the simplex method applied to the CLP-$\Re$ satisfiability problem. The algorithm differs from the one used in the original implementation of CLP-$\Re$ in that it cleanly separates the work of Gaussian elimination and the simplex method, it delays back substitution until the end of a solution path, and it is easily adapted into the parallel execution models we propose. We present two backtracking strategies. In the first scheme, equations are zonestamped, and backtracking entails popping an equation's stack of previous forms. In the second scheme, row operations are accumulated in a backtrack matrix, and backtracking entails matrix multiplication. We prove that when a conflict is uncovered during forward elimination, the backtrack matrix identifies a unique minimal conflict set of equations. We also prove that when a conflict appears during the simplex procedure, a minimal conflict set is similarly generated in the backtrack matrix. We show that this minimal conflict set can be used as a basis for intelligent backtracking. We adapt a scheme for generator-consumer and-parallelism to the context of CLP-$\Re$ execution, and show how the intelligent backtracking already inherent in the generator-consumer approach is enhanced with knowledge of minimal conflict sets. Our algorithm for constraint satisfaction is also incorporated into a variety of parallel execution models which assume a left-right-depth-first traversal of the search tree. One execution model pipelines equations from the inference engine to the solver, looks ahead to the next goal, and then synchronizes with the solver before entering the next cause. Another execution model pipelines equations similarly, but synchronizes only at the end of a solution path. We have implemented the second model described, and we draw conclusions from performance results.