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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 18649921 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Menezes%2C+Francisco%22">Menezes, Francisco</searchLink><relatesTo>1</relatesTo><i> fm@fct.unl.pt</i><br /><searchLink fieldCode="AR" term="%22Barahona%2C+Pedro%22">Barahona, Pedro</searchLink><relatesTo>1</relatesTo><i> pb@fct.unl.pt</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Annals+of+Operations+Research%22">Annals of Operations Research</searchLink>. 1994, Vol. 50 Issue 1-4, p411-426. 16p. 4 Diagrams, 4 Charts. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Logic+programming+languages%22">Logic programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Prolog+%28Computer+program+language%29%22">Prolog (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22CSP+%28Computer+program+language%29%22">CSP (Computer program language)</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Heuristic%22">Heuristic</searchLink><br /><searchLink fieldCode="DE" term="%22Operations+research%22">Operations research</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=18649921 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/BF02085650 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 16 StartPage: 411 Subjects: – SubjectFull: Logic programming languages Type: general – SubjectFull: Prolog (Computer program language) Type: general – SubjectFull: CSP (Computer program language) Type: general – SubjectFull: Computational complexity Type: general – SubjectFull: Heuristic Type: general – SubjectFull: Operations research Type: general Titles: – TitleFull: Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Menezes, Francisco – PersonEntity: Name: NameFull: Barahona, Pedro IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 04 Text: 1994 Type: published Y: 1994 Identifiers: – Type: issn-print Value: 02545330 Numbering: – Type: volume Value: 50 – Type: issue Value: 1-4 Titles: – TitleFull: Annals of Operations Research Type: main |
| ResultId | 1 |
