RUI: Strategies for Fast Execution of Constraint Logic Programs Over a Real-Number Domain

约束逻辑编程是一种声明性编程范式，已被证明对调度、空中交通流量管理、动态物理系统模拟、微分方程组求解和期权交易分析等计算困难的问题具有良好的表达能力。然而，尽管CLP语言具有很强的表现力，但对于它们所应用的问题，它们的执行效率并不总是足够高。这项研究的目标是开发快速执行约束逻辑程序的策略，特别是在实数或有理算术约束领域。为此，比较了基于高斯消元的增量约束满足算法和基于单纯形的约束满足算法在CLP环境下的效率；研究了智能回溯和独立AND并行的可行性；继续研究推理机和求解器的异步并行执行；并正在开发用于约束求解的并行增量算法。该研究项目有很强的本科生参与度和研究内容。学生参与算法的设计、实现和测试，并接触到来自计算理论、编程语言设计、线性规划问题、人工智能搜索和回溯策略以及并行计算的概念。

Constraint logic programming is a declarative programming paradigm which has proven to be expressive for computationally difficult problems such as scheduling, air traffic flow management, simulation of dynamic physical systems, solution of differential equations, and options trading analysis. However, while CLP languages are expressive, their execution is not always efficient enough for the problems to which they apply. The goal of this research is to develop strategies for fast execution of constraint logic programs, particularly in the domain of real or rational arithmetic constraints. To this end, incremental Gaussian elimination-based and simplex-based constraint satisfaction algorithms are compared for their efficiency in the context of CLP; the feasibility of intelligent backtracking and independent and-parallelism is investigated; work on asynchronous parallel execution of the inference engine and solver is continued; and parallel incremental algorithms for constraint solving are being developed. The research program has strong undergraduate involvement and research components. Students are involved in the design, implementation, and testing of algorithms, and are exposed to concepts from the theory of computation, programming language design, the linear programming problem, AI search and backtracking strategies, and parallel computation.