Preuves de non realisabilite et filtrage de domaines pour les problemes de satisfaction de contraintes: Application a la confection d'horaires.

摘要

A significant number of large and very constrained problems, be it theoretical or applied, have no solution that satisfies all the constraints. The present work focuses on this kind of problems that can be modeled as constraint satisfaction problems (CSP). We will be particularly interested in investigating the causes of impossibility of a feasible solution. Explaining the causes of failure to achieve a feasible solution is in fact extremely important and useful; since it may allow us to reformulate the original problem and transform it into a problem with a feasible solution.;On the other hand, for some of the feasible problems, it also frequently happens that a value in the domain of a variable is impossible in the sense that there is no solution verifying all the constraints in which the variable has this value. In those cases, we want to be able to delete these impossible values from the domains of the variables. Such a technique is called domain filtering and will be studied for a specific global CSP constraint: the SomeDifferent constraint.;This thesis has two main goals. The first goal is to implement tools that automatically detect the infeasible irreducible subsets of constraints or variables for infeasible problems. Such algorithms will be adapted for two problems: the boolean satisfiability problem and a crew scheduling problem. The second goal is to develop a domain filtering algorithm for feasible problems.;As the considered problems are very constrained and of large size, we will use tabu search heuristics in our algorithms to extract infeasible irreducible subsets of constraints or variables in infeasible problems, and to detect impossible values in the domains of the variables in feasible problems. Then, we will use exact algorithms to validate the results produced by our heuristic methods.;For that purpose, we wish to detect smaller, incoherent and irreducible subproblems of the considered infeasible problem. We will call such subsets infeasible irreducible subsets (IIS) of constraints or variables. As a theoretical example, we will study the boolean satisfiability problem. And as a practical example, we will consider a crew scheduling problem, for which managers in charge of building a schedule would like to be able to detect the reasons of an infeasibility, in order to modify some of the constraints and obtain a feasible schedule.;The first part of the thesis focuses on the search of infeasible irreducible subsets of constraints and variables for the boolean satisfiability problem commonly called SAT problem.;The second part of the thesis presents a domain filtering algorithm for the SomeDifferent constraint.;Finally, in the third part, the detection tools of infeasible irreducible subsets of constraints are applied to a crew scheduling problem.