Constraint programming: models and algorithms

约束编程：模型和算法

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

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. These tasks range from ones that are simple for humans, such as vision and language comprehension, to ones that are difficult for humans, such as 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 constraint programming research projects that fall within the solving stage. A key to improving many applications of constraint programming is to improve the underlying search algorithms. Much progress has been made recently, but more work remains to be done. I propose several projects for improving backtracking search, the most commonly used form of search for solving constraint models, as well as a project investigating an alternative to backtracking search. In addition to this more theoretical and experimental work, I propose to continue an application-driven research project on effectively solving real-world optimization problems. Focusing on applications has had the benefit of identifying shortcomings in existing constraint programming approaches as well as making a contribution to the practice of constraint programming.

约束编程是解决困难问题的强大框架。在约束规划方法中，通过对可接受的解决方案陈述约束来建模问题。一旦模型被公式化，各种算法---通常基于搜索---可用于求解模型。有许多有趣的任务，这种方法特别适合。这些任务范围从对人类来说简单的任务（如视觉和语言理解）到对人类来说困难的任务（如日程安排和计划）。这些任务的共同点是，约束是问题的自然组成部分。一个很好的例子是安排人或机器。什么是现成的是限制，如工人只能在一周的某些部分或只能做某些工作。我建议约束编程的研究项目，属于解决阶段。改进约束规划的许多应用的关键是改进底层搜索算法。最近取得了很大进展，但仍有更多工作要做。我提出了几个项目，以改善回溯搜索，最常用的搜索形式，解决约束模型，以及一个项目调查的替代回溯搜索。除了这个更多的理论和实验工作，我建议继续有效地解决现实世界的优化问题的应用驱动的研究项目。注重应用程序的好处是确定现有的约束编程方法的缺点，以及作出贡献的约束编程的做法。