Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently.
Saved in:
| Title: | Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently. |
|---|---|
| Authors: | Menezes, Francisco1 fm@fct.unl.pt, Barahona, Pedro1 pb@fct.unl.pt |
| Source: | Annals of Operations Research. 1994, Vol. 50 Issue 1-4, p411-426. 16p. 4 Diagrams, 4 Charts. |
| Subjects: | Logic programming languages, Prolog (Computer program language), CSP (Computer program language), Computational complexity, Heuristic, Operations research |
| Abstract: | Logic programming languages, such as PROLOG, allow a declarative specification of Constraint Satisfaction Problems (CSPs), freeing the user from specifying more or less complex control directives. However, the price to pay for such flexibility is a loss of efficiency, which makes Logic Programming inadequate to solve CSPs of even moderate size and complexity. To extend the range of applicability of logic programming, several improvements have been proposed. The use of heuristics is one such improvement. Although this usually forces the user to specify some form of control (thus abandoning the pure declarative nature of a logic program), these specifications can be made declarative by making use of some appropriate meta-predicates. Another extension to logic programming that improves its efficiency, is the active use of constraints, as done in the various formulations of constraint logic programming languages. In particular, the use of finite domains is quite adequate to implement look-ahead schemes to efficiently solve several types of CSPs. In this paper, we discuss the complementary nature of heuristics and look-ahead schemes and present a constraint logic programming framework that integrates both these techniques. Results obtained with a time-tabling problem executed on a prototype that implements such a framework are presented, and show that significant efficiency improvements can be achieved when compared with the separate use of the two techniques. [ABSTRACT FROM AUTHOR] |
| Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
