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