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

点击翻译按钮获取中文摘要

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. ***