A solution of a CSP is an assignment of a value to each variable from its domain such that all constraints are satisfied. A CSP is solvable if it has at least one solution. A subset of constraints is infeasible if no assignment can satisfy all these constraints simultaneously. An irreducible inconsistent set (IIS) of constraints is an infeasible set of constraints that becomes feasible when any one constraint is removed. Similarly, a subset of variables is infeasible if all possible assignments violate at least one constraint involving only variables of this subset. An irreducible inconsistent set (IIS) of variables is an infeasible set of variables that becomes feasible when any one variable is removed. We describe three systematic approaches to generate IISs of constraints or variables. These approaches are illustrated on some CSPs, including the k-coloring problem.

Cardinality and Sequencing constraints have proved very useful in many real-life problems such as rostering or car sequencing problems. Cardinality Constraints are used to define the number of times some values can appear in a solution, for instance, to state that a nurse can work at least 2 nights per month and at most 8. Sequence constraints are used to express cardinality constraints on sequences of consecutive variables, that is constraints such as: every sequence of 7 days of work must contain at least 2 days off. In this paper we propose an efficient and original way to combine these constraints. A new global constraint is then defined. The filtering algorithm associated with this constraint, that is an algorithm which aims to remove inconsistent values, is based on the resolution of a b-matching problem, also called degree constrained subgraph problem. Thanks to this new constraint some open problems of the CSPLIB have been solved.

The probabilistic satisfiability problem (PSAT), in decision form, is the following: given logical sentences S₁, S₂, ... S_m from the propositional calculus together with probabilities that they are true, find whether these probabilities are coherent or not. In its optimization form, the problem is the following: given an additional sentence S_m+1, find the best possible bounds on its probability of being true. Both versions are due to George Boole (1854) and are basic to Artificial Intelligence. Two approaches for solving PSAT are much studied: they are rule-based and linear-programming based. The former provides a justification of the results obtained, but may not converge or be able to detect incoherence. The latter approach gives guaranteed results but may be time-consuming. We show that merging both approaches is beneficial for the two of them: using first a rule-based heuristic provides provisional conclusions; then a compact linear program, with rows associated with the rules used, provides estimates of dual variables at the optimum. Using these in a stabilized column generation scheme confirms results or gets optimal ones in less time than with the usual linear programming approach. Computational results illustrate the advantages of the merging.