Constraint programming: models and 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.