Design of generic and robust search heuristic in constraint programming to solve practical combinatorial problems

这项研究计划旨在为改进的计算机化方法开发新的算法，以解决在许多人类活动领域发生的具有重要经济和社会影响的复杂规划问题。这类问题的例子包括员工日程安排、体育日程安排、电信设计和运输物流。在这些领域中遇到的具体组合问题据说很难以令人满意的方式解决。约束规划是解决组合问题的一种强有力的技术。它使用复杂的推理来减少搜索空间，但到目前为止，它缺乏通用和健壮的搜索启发式方法。这使得后一种技术在易用性方面处于劣势，尽管其建模灵活性是解决现实工业问题的一项资产。全局约束在约束编程中发挥了核心作用，因为它们捕获了问题的关键子结构，并有效地利用它们来促进推理。这项研究项目提出了对搜索做同样的事情。约束编程中的大多数通用动态搜索启发式算法依赖于单个变量的细粒度级别的信息，而我们研究的动态搜索启发式算法基于更粗略但更全局的信息。所提出的搜索启发式方法围绕着单个约束的解的数目的知识，直觉地认为解很少的约束对应于问题的关于可满足性的关键部分。

This research program aims to develop new algorithms for improved computerized methods to solve complexplanning problems that occur in a number of areas of human activity, with important economic and socialimpacts. Examples of such problems are employee scheduling, sports scheduling, telecommunications design,and transportation logistics. The concrete combinatorial problems encountered in these areas are reputedly verydifficult to solve in a satisfactory manner.Constraint Programming is a powerful technique to solve combinatorial problems. It applies sophisticatedinference to reduce the search space but, to date, lacks a generic and robust search heuristic. Thisputs the latter technology at a disadvantage in terms of ease of use even though its modeling flexibility is anasset to address realistic industrial problems.Global constraints have played a central role in Constraint Programming because they capture keysubstructures of a problem and efficiently exploit them to boost inference. This research project proposes doingthe same thing for search. Whereas most generic dynamic search heuristics in constraint programming rely oninformation at the fine-grained level of individual variables, we investigate dynamicsearch heuristics based on coarser, but more global, information. The search heuristics proposed revolvearound the knowledge of the number of solutions for individual constraints, the intuition being that a constraintwith few solutions corresponds to a critical part of the problem with respect to satisfiability.