Formulations linéaires pour la programmation par contraintes

National audienceDans ce papier, nous présentons dans un premier temps des techniques génériques permettant de formuler toute contrainte d'un CSP comme un Programme Linéaire en Nombres Entiers (PLNE). Cela conduit à exploiter en Programmation Par Contraintes (PPC) de nombreux outils algorithmiques proposés par la communauté de la Recherche Opérationnelle (RO) dans le but, par exemple, de développer des contraintes globales. Ensuite, nous proposons un modèle linéaire générique pour améliorer la technique de filtrage basée sur les coûts réduits [5]. La résolution de ce modèle linéaire permet de calculer des coûts réduits plus intéressants que ceux calculés en résolvant la relaxation continue classique d'un PLNE