Constraint Programming for Probabilistic Reasoning and Compiler Optimization

概率推理和编译器优化的约束编程

• 批准号: 105446-2012
• 负责人: vanBeek, Peter
• 金额: $ 2.04万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569053
• 关键词: Constraint; Programming; Probabilistic; Reasoning; Compiler

Constraint programming is a powerful framework for solving difficult problems. In the constraint programming methodology, one models a problem by stating constraints on acceptable solutions. Once a model has been formulated, various algorithms---usually based on search---are available for solving the model. There are many interesting tasks for which this approach is particularly suited, including sequencing, scheduling, and planning. What these tasks have in common is that constraints are a natural part of the problem. A good example is scheduling people or machines. What is readily available are constraints such as a worker is only available for certain parts of the week or only able to do certain jobs. I propose research projects that both contribute to the foundations of constraint programming and to applications of constraint programming. The applications that I consider include software for handheld devices, where the primary goals are faster performance and lower power consumption. Focusing the research by considering important applications has several benefits. First, it allows us to contribute to the application areas themselves. Second, it allows us to identify---and subsequently overcome---shortcomings in existing constraint programming approaches and so contribute to the foundations of constraint programming. Finally, it extends the practice of constraint programming to new areas.

约束编程是解决困难问题的强大框架。在约束编程方法中，人们通过陈述对可接受解的约束来对问题建模。一旦建立了模型，各种算法-通常基于搜索-可用于求解该模型。这种方法特别适合于许多有趣的任务，包括排序、调度和计划。这些任务的共同点是，约束是问题的自然部分。调度人员或机器就是一个很好的例子。容易得到的是一些限制，比如工人只在一周的某些时间有空，或者只能做某些工作。 我提出的研究项目既有助于约束编程的基础，也有助于约束编程的应用。我考虑的应用包括用于手持设备的软件，其主要目标是更快的性能和更低的功耗。通过考虑重要的应用来集中研究有几个好处。首先，它允许我们为应用领域本身做出贡献。其次，它使我们能够识别-并随后克服--现有约束编程方法中的缺陷，从而为约束编程的基础做出贡献。最后，它将约束编程的实践扩展到新的领域。