This article presents a basic scheme for deriving systematicallya filtering algorithm from the graph properties based representationof global constraints. This scheme is based on thebounds of the graph parameters used in the description ofa global constraint. The article provides bounds for the most commonused graph parameters.

The NP-hard problem of car sequencing has received a lot of attention these last years. Whereas a directapproach based on integer programming or constraint programming is generally fruitless when the number of vehicles tosequence exceeds the hundred, several heuristics have shown their efficiency. In this paper, very large-scaleneighborhood improvement techniques based on integer programming and linear assignment are presented for solving carsequencing problems. The effectiveness of this approach is demonstrated through an experimental study made on seminalCSPlib's benchmarks.

L'identification de structures propres à un problème est souvent une étapeclef pour la conception d'heuristiques de recherche comme pour la compréhension de lacomplexité du problème. De nombreuses approches en Recherche Opérationnelleemploient des stratégies de relaxation ou de décomposition dès lors quecertaines struc-tures idoines ont été identifiées. L'étape suivante est laconception d'algorithmes de résolution qui puissent intégrer à la volée,pendant la résolution, ce type d'information. Cet article propose d'utiliser unsolveur de contraintes à base d'explications pour collecter une informationpertinente sur les structures dynamiques et statiques inhérentes au problème.