Applications and Efficient Execution of Constraint Logic Programming Over a Real-Number Domain

实数域约束逻辑编程的应用和高效执行

• 批准号: 9619523
• 负责人: Jennifer Burg
• 金额: --
• 依托单位: Wake Forest University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-09-01 至 2000-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9619523&HistoricalAwards=false
• 关键词: Applications; Efficient; Execution; Constraint; Logic

9619523 Constraint logic programming (CLP) is a family of programming languages built upon predicate calculus, with the added expressiveness of constraint-based problem representations. Each language in the family is distinguished by the domain of values for the program variables. Prolog is the best-known language in the family and can be viewed as CLP in the domain of infinite trees. This research focuses on CLP over a real-number domain (CLP(R)). Implementations of CLP(R) generally restrict constraints to linear equations and inequalities, and the resulting languages have proven expressive enough for a variety of scheduling, warehouse location, cutting stock, options trading, and crew rostering problems, as well as AI puzzles. However, CLP(R)'s usefulness is limited by the large search space required for most problems and by the complexity of the constraint satisfaction algorithm. Stated more simply, it is not always possible to benefit from CLP's expressiveness, since many useful problems take too long to solve. The goal of this research is to identify CLP(R) applications that would be feasible if execution could be sped up, and to find ways to cut down on execution time through a more efficient constraint satisfaction algorithm. ***

9619523 约束逻辑编程 (CLP) 是一系列基于谓词演算构建的编程语言，增加了基于约束的问题表示的表达能力。该族中的每种语言都通过程序变量的值域来区分。 Prolog 是该家族中最著名的语言，可以被视为无限树领域的 CLP。本研究重点关注实数域上的 CLP (CLP(R))。 CLP(R) 的实现通常将约束限制在线性方程和不等式上，并且事实证明，由此产生的语言对于各种调度、仓库位置、库存削减、期权交易和人员排班问题以及人工智能难题具有足够的表现力。然而，CLP(R) 的实用性受到大多数问题所需的大搜索空间以及约束满足算法的复杂性的限制。更简单地说，并不总是能够从 CLP 的表达能力中受益，因为许多有用的问题需要很长时间才能解决。本研究的目标是确定如果可以加快执行速度则可行的 CLP(R) 应用程序，并找到通过更有效的约束满足算法来减少执行时间的方法。 ***