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.