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.