Intelligent Backtracking for CLP Languages: An Application to CLP(R)
Abstract
Constraint Logic Programming languages such as BNR-Prolog, CHIP, CLP(R) or Prolog III have already shown how useful they can be when wishing to express and solve difficult problems. However, when strongly combinatorial problems are tackled, the standard Prolog exhaustive search mechanism may become prohibitive in terms of computation time. This article explains how an intelligent backtracking algorithm can improve the performance of CLP languages in general and CLP(R) in particular.
First, the usefulness of implementing intelligent backtracking within a CLP language is shown. A version of the Depth-first Intelligent Backtracking method generalized to any CLP language is then described. This method is heavily dependent on a constraint solving algorithm able to find a conflict when the constraint set is not solvable. Many conflicts can explain the inconsistency of a constraint set, and the choice of one of them is an impor- tant and difficult point. The class of "good" conflicts is identified. Choosing a conflict belonging to this class both eases the conflict gener- ation and improves the backtracking strategy. For efficiency, it is shown that only "good" conflicts, should be returned by the constraint solving algorithm.
Finally, the case of CLP(R) is then studied in more detail, with emphasis on a real linear constraint solving algorithm. This algorithm is particularly useful for intelligent backtracking since it can discover minimal conflicts among constraints without any overhead. What is more, this algorithm can easily be extended to find a "good' conflict at low cost.
First, the usefulness of implementing intelligent backtracking within a CLP language is shown. A version of the Depth-first Intelligent Backtracking method generalized to any CLP language is then described. This method is heavily dependent on a constraint solving algorithm able to find a conflict when the constraint set is not solvable. Many conflicts can explain the inconsistency of a constraint set, and the choice of one of them is an impor- tant and difficult point. The class of "good" conflicts is identified. Choosing a conflict belonging to this class both eases the conflict gener- ation and improves the backtracking strategy. For efficiency, it is shown that only "good" conflicts, should be returned by the constraint solving algorithm.
Finally, the case of CLP(R) is then studied in more detail, with emphasis on a real linear constraint solving algorithm. This algorithm is particularly useful for intelligent backtracking since it can discover minimal conflicts among constraints without any overhead. What is more, this algorithm can easily be extended to find a "good' conflict at low cost.
