Abstract FR:

Cette these est une contribution a la resolution de contraintes lineaires en programmation logique par contraintes (clp). Nous resolvons les contraintes lineaires simples exprimees avec les symboles de relation =, , < et = (different). Nous resolvons egalement des contraintes lineaires complexes. Celles-ci permettent de raisonner sur la valeur de verite d'une contrainte et d'exprimer, par exemple, des relations booleennes sur les contraintes lineaires. Le traitement des contraintes complexes s'appuie sur la verification de l'implication de contraintes simples. Nous avons, pour cela, introduit des formes particulieres pour ces dernieres dont les proprietes permettent de simplifier cette verification. L'algorithme de resolution est essentiellement base sur le simplex revise, qui est plus efficace sur les problemes pratiques que les algorithmes utilises jusqu'alors dans les langages clp. Cet algorithme est dynamique : il est possible d'ajouter incrementalement une contrainte au systeme de contraintes courant et de retirer, a tout moment, une contrainte quelconque de ce systeme. Les contraintes < et = sont traitees grace a l'identification des variables figees. On presente ici une synthese comparative des differentes methodes utilisees pour cette identification en etudiant particulierement leur adaptation a l'algorithme du simplex revise. Finalement, l'algorithme de resolution a ete integre a un langage clp et ses performances ont ete evaluees sur des problemes pratiques de recherche operationnelle.