Résumé
Pour résoudre des problèmes linéaires sur les entiers, une approche largement utilisée consiste a effectuer une recherche globale par séparation et évaluation a travers toutes les combinaisons possibles. Du fait de l'aspect fortement combinatoire du problème, cette recherche est controlée par un solveur de contraintes qui utilise les contraintes pour réduire a priori l'espace de recherche.
On introduit dans cet article un nouveau solveur basé sur la
coopération de solveurs linéaires sur les réels. L'idée
est d'utiliser un ensemble de solveurs linéaires pour calculer les
domaines des variables sur les réels, puis de réduire ces
domaines a l'intervalle entier inclus le plus proche. Ce filtrage est effectué
jusqu'a atteindre un point fixe ou tous les domaines sont bornés
par des entiers appartenant a l'espace des solutions sur les réels.
Ce point fixe correspond a une nouvelle consistance partielle qui permet
de résoudre des problèmes plus efficacement, en nombre de
points de choix mais aussi en temps.
Full paper (postscript)