Ajout d'une contrainte dans la programmation de contraintes

Question

Est-il vrai que plus on ajoute de contrainte à un solveur de programmation par contraintes, plus il sera efficace? Comment cela se compare-t-il à l'ajout de contraintes dans les solveurs de programmation d'entiers.

Answer 1

Ce n'est pas vrai en pratique. De plus, c'est quelque chose de presque impossible à deviner sans expérimenter. En effet, l'ajout de contraintes (prouvées mathématiquement valides, ou simplement devinées par votre flair et votre sentiment d'entreprise) à un modèle d'optimisation mathématique qui est résolu par des techniques de programmation par contraintes ou des techniques de programmation d'entiers devrait être bon pour couper certaines branches de l'arbre d'énumération (c'est-à-dire l'énumération des solutions partielles), en améliorant la propagation des contraintes et / ou la relaxation continue. D'un autre côté, les solveurs de programmation par contraintes et les résolveurs de programmation par nombres entiers reposent désormais sur de nombreux ingrédients heuristiques; l'ajout de contraintes peut être mauvais pour ces heuristiques. En conclusion, parfois c'est bien, parfois pas ;-) Prenez le temps d'expérimenter sur les instances à résoudre.